Czy rzeczywiście można mieć „użyteczny” język programowania, który nie jest kompletny w Turingu?

37

Jeżeli przyjmuje się, że język musi być kompletny Turinga, aby był dobry, to czy rzeczywiście można mieć „użyteczny” język programowania, który nie jest kompletny?

Powinienem wyjaśnić, że chodzi tu raczej o języki programowania w tradycyjnym znaczeniu, a nie o języki znaczników i zapytań.

PhonicUK
źródło
3
@PhonicUK SQL na początku nie był w pełni ukończony
Ryathal
4
@Ryathal SQL nie jest językiem programowania, to język zapytań.
yannis
2
@PhonicUK Twoje pytanie w komentarzu jest naprawdę opłacalne, zmień postawione pytanie na to lub zostanie zamknięte, ponieważ nie jest konstruktywne. W rzeczywistości istnieją użyteczne, niekompletne języki, i chciałbym poznać ich szczegóły.
Jimmy Hoffa
5
regex nie jest jeszcze ukończony, ale jest powszechnie używany
maniak zapadkowy
3
@DavidHammen Rzeczywiste implementacje są ograniczone, tak, ze względu na ograniczenia naszego fizycznego wszechświata (może budować tylko skończoną pamięć, może uruchamiać maszynę tylko przez ograniczony czas, zanim ulegnie awarii). Ale to nie znaczy, że języki są ograniczone. IOW specyfikacja pełnego języka turinga nie wymaga implementacji od nałożenia takich ograniczeń na program, podczas gdy język inny niż TC wymaga na przykład dowodu wypowiedzenia.

Odpowiedzi:

48

Coq , Agda , HOL i ACL2 są bardzo przydatnymi i niezwykle potężnymi językami, chociaż nie są kompletne w Turingu .

Powszechną cechą, która czyni je niekompletnymi, jest fakt, że zawsze można udowodnić zakończenie. Wystarczy bardzo proste ograniczenie: połączenia rekurencyjne są dozwolone tylko na możliwych do udowodnienia strukturalnie mniejszych warunkach. Dlatego, gdy nie jest to możliwe do wykonania tłumacza języka Turinga uzupełniania lub nawet dla języka sama wiele innych przydatnych rzeczy są nadal możliwe, jak kwalifikowanego kompilatora C .

Logika SK
źródło
2
Czy dla tych, którzy nie znają tych języków, mógłbyś bardziej szczegółowo opisać to, czego brakuje, co sprawia, że ​​nie są kompletne w Turingu, a także kilka przykładów rzeczy zbudowanych w tych językach?
PhonicUK
8
@PhonicUK: C kompilator nie jest implementacja C . Jest to narzędzie, które przekształca kod z jednego języka (C) w inny (zwykle kod maszynowy). Że nie nie oznacza, że kompilator C Sam jest równoznaczne z dowolnej losowej programie C.
Joachim Sauer
9
@ PhonicUK, nie można zaimplementować tłumacza języka kompletnego Turinga w języku niekompletnym. Ale możesz oczywiście zaimplementować kompilator (ponieważ procesor z procesami Turinga dokona rzeczywistej oceny).
SK-logic
11
@ SK-logic: „Oczywiście?” Jest to możliwe tylko dla C, ponieważ jest to dość prosty język. Nie jest to możliwe w C ++, ponieważ kompilator musi interpretować kod szablonu (który jest kompletny w czasie Turinga).
MSalters
11
@MSalters Tak, jeśli kompilacja języka jest zakończona, kompilator musi być napisany w pełnym języku. Co jest również dość oczywiste (żeby nie powiedzieć tautologiczne). Należy jednak pamiętać, że standard C ++ dopuszcza ograniczenia dla programów wejściowych, takie jak maksymalna głębokość oceny dla instancji szablonów (i istniejące implementacje korzystają z tej wolności). Jeśli się nie mylę, oznacza to, że może być możliwy niekompletny kompilator C ++ (oczywiście wykluczając niezwiązane ze sobą problemy).
12

Sądzę, że termin „mini-język” Yegge odnosi się do faktu, że często użyteczne jest używanie języka do konkretnych problemów, w których język nie wymaga kompletności w celu wykonania zadania, a to dotyczy sedna tego, jak bardzo - użyteczne mogą być kompletne języki. https://sites.google.com/site/steveyegge2/language-grubbing

Wikipedia odpowiada na to bardzo dobrze, zgodnie z tym, co powiedział mój brzuch. Najpierw myślałem o czystej matematyce, a potem przypomniałem sobie o wyrażeniach regularnych, a Wikipedia wymienia Epigram, który moim zdaniem byłby w stylu „czystej matematyki”.

http://en.wikipedia.org/wiki/Turing_completeness#Non-Turing-complete_languages

Języki niekompletne

Istnieje wiele języków obliczeniowych, które nie są kompletne w Turingu. Jednym z takich przykładów jest zestaw języków regularnych, najczęściej wyrażeń regularnych, które są generowane przez automaty skończone. Potężniejszym, ale wciąż niepełnym rozszerzeniem automatów skończonych Turinga jest kategoria automatów wypychających i gramatyk bezkontekstowych, które są powszechnie używane do generowania parsowania drzew w początkowej fazie kompilacji programu. Dalsze przykłady obejmują niektóre wczesne wersje języków modułu cieniującego piksele osadzone w rozszerzeniach Direct3D i OpenGL, lub szereg formuł matematycznych w arkuszu kalkulacyjnym bez cykli. [Potrzebne źródło] We wszystkich funkcjonalnych językach programowania wszystkie funkcje są całkowite i muszą zakończyć, na przykład Charity i Epigram. Organizacja charytatywna wykorzystuje system typów i konstrukcje kontrolne oparte na teorii kategorii,

Języki danych

Pojęcie kompletności Turinga nie ma zastosowania do takich języków, jak XML, JSON, YAML i wyrażenia S, ponieważ są one zwykle używane do reprezentowania danych strukturalnych, a nie opisywania obliczeń. Są one czasami określane jako języki znaczników, a dokładniej jako „języki opisu danych”.

Wspomina również, że reprezentacje struktury danych nie są językami, ale sądzę, że XSLT powinien liczyć się jako reprezentacja obliczeń, XPath może nie opierać się na tym, co powiedział Yannis o SQL jako języku zapytań, a nie języku obliczeń. Być może T-SQL lub PL / SQL liczą się jako języki obliczeniowe, ponieważ można wykonać wiele obliczeń przy użyciu ich agregatów, gdzie uogólniona forma SQL może nie określać agregatów.

Jimmy Hoffa
źródło
8

Rozumiem, że SQL jest dość popularny wśród typów biznesowych

Martin Beckett
źródło
3
SQL to język zapytań, a nie język programowania.
PhonicUK
4
@PhonicUK: a jaka dokładnie jest różnica między językiem zapytań a językiem programowania?
Joachim Sauer
8
@PhonicUK - Tex jest język znaczników tekstu i to kompletne Turinga
Martin Beckett
3
nowoczesne wdrożenia sql, o ile mi wiadomo, są już ukończone.
shabunc
6
@shabunc IIRC tylko z procedurami przechowywanymi. Argumentacja staje się nieco okrągła, jeśli nie jest zakończona Turinga, to nie jest to język programowania - dlatego wszystkie języki „programowania” to TC
Martin Beckett
5

Kompletność Turinga jest niezbędna, aby język mógł być używany jako język ogólnego przeznaczenia. Ale to nie wystarcza , tj. Tylko dlatego, że jest kompletne Turinga, nie nadaje się do każdej problematycznej dziedziny:

  • Udowodniono, że biała spacja jest kompletna, ale w oczywisty sposób nie nadaje się do żadnej problematycznej dziedziny poza rozrywką dla programistów.
  • Udowodniono, że szablony C ++ są kompletne, ale tak naprawdę nigdy nie napisałbyś z nimi całych programów.

I odwrotnie, DSL jest odpowiedni dla problematycznej dziedziny, dla której został zaprojektowany (zakładając, że został właściwie zaprojektowany), nawet bez kompletności Turinga:

  • HTML * zapewnia zwięzły sposób opisu drzewa DOM. Chociaż JavaScript jest w pełni ukończony i można go używać do tego samego, jest o wiele głośniejszy i niejasny
  • XPath i inne języki zapytań, PCRE bez osadzonego kodu i takie są potężnymi narzędziami do pojedynczego zadania, dla którego zostały zaprojektowane

* IIRC udowodniono, że HTML z animacjami CSS jest w pełni Turinga, wykorzystując je do implementacji Gry życia Conwaya na szeregu pól wyboru. Ale przydatność HTML-u utrzymuje się nawet w przeglądarkach, które nie obsługują animacji CSS.

back2dos
źródło
2
Czy masz link do Conway's Life zaimplementowany w CSS?
RBerteig
Nie znam implementacji CGOL w CSS, ale wiem, że reguła 110 została zaimplementowana. Wydaje się, że nie można go znaleźć, wydaje się, że został przeniesiony.
Christian Mann
-1 Bardzo interesujące, ale nie odnosi się do
zadanego
2
@mattnz: Wrong. Podaję konkretne przykłady użytecznych niekompletnych języków, które moim zdaniem są właściwą odpowiedzią na „Czy rzeczywiście można mieć„ użyteczny ”język programowania, który nie jest kompletny w Turingu?”, Podobnie jak inna odpowiedź tutaj
back2dos
3

W rzeczywistości istnieją języki programowania, w których można pisać tylko „wydajne” programy. Wydajny w tym sensie oznacza, że ​​każdy program napisany w takim języku reprezentuje język P. Bellantoni, Niggl i Schwichtenberg opisują tutaj taki język .

SpaceTrucker
źródło
1

Preprocesor C nie jest Turing-complete (z założenia), ale wciąż może implementować interpreter dla języka, który jest Turinga kompletny (Zamówienie języka, jak opisano w dokumentacji, jest w zasadzie tylko zbiorem frezować czysto funkcjonalny program typu ML / Scheme i byłby stosunkowo mało znaczący - prawdopodobnie całkiem przyjemny w użyciu - gdyby nie nietypowa implementacja).

Trik za tym jest podobny do argumentów powyżej dotyczących implementacji dowolnej maszyny Turinga w skończonym fizycznym wszechświecie: preprocesor C nie może zapewnić nieskończonej liczby kroków lub komórek danych dla języka, ale może:

  1. zapewnienie bezzasadnie dużą liczbę dynamicznego (2 ^ 64 lub tak domyślnie), wystarczająco duży dla rozwiązywania problemów przy użyciu najbardziej realistyczny gwałtowny proces ekspansji ( bełkot bełkot dożywotnią wszechświata Mumble ).

  2. użyj dowolnego statycznego ograniczenia dla powyższej liczby, tzn. chociaż liczba kroków musi być pewną liczbą skończoną, możesz zmienić to, co jest określone ograniczenie w czasie „kompilacji”, zmieniając ustawienia statyczne silnika interpretera. Ponieważ nie ma (teoretycznego) ograniczenia rzeczywistej wartości tego ograniczenia, można (teoretycznie) rozszerzyć, aby pasował do miejsca wymaganego przez dowolny program kończący.

Nie twierdząc, że Order jest koniecznie sam w sobie „użyteczny”, lub że jakikolwiek silnik implementowany przez CPP byłby, ale jest to ciekawy dowód koncepcji. Jest również podobno dynamicznie wpisywany , co jest niezwykłe w tym obszarze.

Leushenko
źródło
Głosowanie za mamrotanie w środku wykładu.
jpaugh
-1

Tak, w rzeczywistości możliwe jest posiadanie przydatnego języka, który nie jest kompletny w Turingu. Zobacz tutaj: http://tkatchev.bitbucket.org/tab/examples.html

Innym przykładem przydatnego niekompletnego języka Turinga jest SQL. (A jeszcze innym są arkusze kalkulacyjne, takie jak Gnumeric lub Excel, chociaż tak naprawdę nie są to języki programowania).

Co do tego, dlaczego chcesz mieć język, który nie jest kompletny w Turingu: ponieważ pozwala to na pewne mocne gwarancje dotyczące zachowania w czasie wykonywania.

Mówiąc wprost, kompletność Turinga oznacza zdolność do rekurencji. Posiadanie rekurencji oznacza posiadanie potencjalnie niezwiązanych struktur w pamięci. Ponieważ w prawdziwym świecie pamięć nie jest nieskończona, kompletność Turinga wymaga zarządzania pamięcią i / lub wyrzucania elementów bezużytecznych.

Zakaz rekurencji to świetny sposób na uniknięcie naprawdę trudnego problemu zarządzania zasobami.

Nota bene! Niekompletność Turinga niekoniecznie oznacza, że ​​jakikolwiek program musi się zakończyć. Niekompletny język Turinga może umożliwić ocenę nieskończonej leniwej listy.

tkatchev
źródło
-1

Do tej pory wspomniano o jednym interesującym „języku programowania sub-Turinga”, więc go dodam.

Nazywa się to „Crema” . Opisuje się jako:

Crema to front-end LLVM, którego celem jest specyficzne wykonanie w przestrzeni pod Turinga Complete. Zaprojektowany jako prosty do opanowania i praktyczny dla większości potrzebnych zadań programistycznych, Crema może ograniczyć złożoność obliczeniową programu do minimum niezbędnego do poprawy bezpieczeństwa.

To dość minimalistyczny i raczej niski poziom.

Powinien wyglądać znajomo dla programistów C.

Został początkowo sfinansowany przez Agencję Obrony Zaawansowanych Projektów Badawczych (DARPA), ale w chwili pisania tego tekstu wygląda na zupełnie nieokreślony. Ale może jednak ktoś jest zainteresowany.

Mateusz Kowalewski
źródło