Jasny, kompletny, dowód na to, że język jest konkurencyjny w Turingu?

Widziałem strony internetowe, które rzekomo „dowodzą”, że HTML5 + CSS jest Turing Complete.

Widziałem strony internetowe, które rzekomo „dowodzą”, że SQL jest Turing Complete.

Widziałem kilka stron internetowych, które rzekomo „wyjaśniają”, co to znaczy być Turing Complete.

Wystarczająco!

Gdzie mogę znaleźć książkę (napisaną przez eksperta w dziedzinie teorii obliczeń) lub recenzowany artykuł (w renomowanym czasopiśmie), który pokazuje dowód: „Ten język XYZ jest w stanie opisać maszynę obliczeniową o takiej samej mocy obliczeniowej jako maszyna Turinga?

— Roger Costello
źródło

Żaden ekspert nie napisze takiego artykułu, ponieważ byłoby to bezcelowe.

— Andrej Bauer,

Ale są papiery, które to robią. Zastanów się, że obwody niewrażliwe na quasi-opóźnienie są kompletne Turinga, co ma dowód konstrukcyjny.

— Dan D.

Zjem kapelusz, jeśli znajdziesz artykuł recenzowany, który ma szczegółowy dowód, że HTML5 + CSS, SQL lub PHP są w Turingu kompletne.

— Andrej Bauer,

@ andrej spróbuj tego. wystarczająco blisko? Wersja XSLT 2.0 jest Turing-Complete: dowód oparty wyłącznie na transformacji . może po prostu zjedz swoje warzywa: p

— vzn 30.09.13

zobacz także, co sprawia, że turing jest kompletny , programmers.se

— vzn

Odpowiedzi:

Każdy język, który może zaimplementować dwa liczniki (tj. Dwa rejestry, które mogą przechowywać dwie dowolnie duże liczby całkowite) oraz program utworzony z oznaczoną sekwencją tych dwóch instrukcji elementarnych, jest całkowicie ukończony: $C_1, C_2$

DODAJ do licznika , instrukcja GOTO $1$ $C_i$ $I_j$
SUBTRACT z licznika jeśli i instrukcja GOTO ; w przeciwnym razie (jeśli ) instrukcja GOTO $1$ $C_i$ $C_i > 0$ $I_j$ $C_i = 0$ $I_k$

Wynik jest udowodniony w:

Marvin L. Minsky, „Rekurencyjna nierozwiązywalność problemu posta w tagu i innych tematów w teorii maszyn Turinga” (1961)

Nie zapominaj, że model obliczeniowy (w Twoim przypadku język programowania + urządzenie wykonujące programy napisane w tym języku ) można uznać za zakończony Turing tylko wtedy, gdy obsługuje on dostęp do nieograniczonej ilości pamięci (tj. Miejsca) lub może przechowywać ( w jakiejś formie) dowolnie duże liczby całkowite. Implementacja języka programowania na prawdziwym komputerze jest równoważna automatowi z ograniczeniem liniowym .

Można również znaleźć wiele referencji na stronach Wikipedii na temat modelu RAM i modelu RASP .

Wreszcie fajna książka poświęcona równoważności różnych modeli obliczeń to:

„Modele obliczeń: wprowadzenie do teorii obliczeń” Maribel Fernandez

— Vor
źródło

„Nie zapominaj, że język programowania można uznać za kompletny Turing tylko wtedy, gdy obsługuje on dostęp do nieskończonej pamięci”. Zatem nie może istnieć implementacja języka Turing Complete? Czy to twój wniosek? A może chcesz powiedzieć, że wszystkie (większość) używanych przez nas języków jest Turing Complete, ponieważ ten wymóg jest łatwy do spełnienia? Oba wnioski są aktualne na podstawie Twojej odpowiedzi.

— Bakuriu

bakuriu patrz TM pełna i moc obliczeniowa

— dniu

@ Bakuriu: w rzeczy samej zdanie jest nieco dwuznaczne; Chodzi mi tylko o to, że model obliczeniowy można uznać za kompletny Turinga, jeśli - w jakiejś formie - pozwala na korzystanie z nieograniczonej pamięci. Większość języków programowania jest kompletnie Turinga, ponieważ w ich specyfikacjach (składniowych) nie mają ograniczeń co do wielkości zmiennych lub wskaźników, ale ich implementacje są ograniczone; patrz na przykład C <limit.h>. Więc nawet jeśli masz komputer z niepowiązaną pamięcią, na którym działa implementacja C, nie możesz użyć tej pamięci, chyba że zapewnisz „dodatkowy mechanizm”, który nie jest częścią języka.

— Vor

{w . w ∣ w \in {0, 1}}

$\{w.w \mid w \in \{0, 1\}\}$

Dwa najczęściej używane podręczniki dotyczące teorii obliczalności i złożoności to:

Michael Sipser: Wprowadzenie do teorii obliczeń , 2 / e, Cengage, 2005.

John E Hopcroft; Jeffrey D Ullman: Wprowadzenie do teorii automatów, języków i obliczeń , Addison-Wesley, 1979.

Istnieje również piękna monografia filozoficzna dla laików, która analizuje szczegóły techniczne teorii obliczeń bez formalnych dowodów.

Douglas Hoftstadter: Gödel, Escher, Bach , Basic Books, 1979.

Wreszcie najlepszym wprowadzeniem do obliczalności może być układanka autorstwa znanego logika:

Raymond Smullyan: The Lady or the Tiger and Other Logic Puzzles , Penguin, 1983. (Teraz w niedrogiej edycji Dover, 2009.)

(Zaczyna od szeregu łamigłówek opartych na paradoksie Kłamcy, a następnie pracuje nad konstrukcją autoreferencji w postaci puzzli w stylu Sherlocka Holmesa o tajemniczym zamkniętym pudełku.)

— Wędrująca logika
źródło