Co sprawia, że ​​język Turinga jest kompletny?

Jaki jest minimalny zestaw cech / struktur językowych, które sprawiają, że Turing jest kompletny?

Turing Tarpit jest rodzajem języka programowania ezoterycznej, która stara się być kompletne Turinga podczas używania jako kilka elementów, jak to możliwe. Brainfuck to chyba najbardziej znana tarpit, ale jest ich wiele.

• Iota i Jot są językami funkcjonalnymi, odpowiednio z dwoma i trzema symbolami, w oparciu o rachunek kombinatoryczny SK (I) .

• OISC ( One Instruction Set Computer ) oznacza rodzaj obliczeń imperatywnych, które wymagają tylko jednej instrukcji jednego lub większej liczby argumentów, zwykle „odejmują i rozgałęziają się, jeśli jest mniejsza lub równa zero”, lub „odwracają odejmowanie i pomijają, jeśli pożyczają”. MMU x86 implementuje poprzednią instrukcję i dlatego jest kompletna w Turingu.

Ogólnie rzecz biorąc, aby imperatywny język był kompletny w Turinga, potrzebuje:

1. Postać powtórzeń warunkowej lub skoku warunkowego (na przykład while, if+ goto)

2. Sposób na odczyt i zapis jakiejś formy przechowywania (np. Zmienne, taśma)

Aby język funkcjonalny oparty na rachunku lambda był TC, potrzebuje:

1. Zdolność do abstrakcyjnego działania argumentów (np. Abstrakcja lambda, cytowanie)

2. Możliwość zastosowania funkcji do argumentów (np. Redukcja)

Istnieją oczywiście inne sposoby patrzenia na obliczenia, ale są to popularne modele plandek Turinga. Należy pamiętać, że prawdziwe komputery nie są uniwersalnymi maszynami Turinga, ponieważ nie mają nieograniczonej przestrzeni dyskowej. Ściśle mówiąc, są to „ograniczone urządzenia magazynujące”. Gdybyś ciągle dodawał do nich pamięć, asymptotycznie zbliżyliby się do maszyn Turinga. Jednak nawet ograniczone maszyny magazynujące i maszyny o stanie skończonym są przydatne do obliczeń; po prostu nie są uniwersalne .

Ściśle mówiąc, we / wy nie jest wymagane dla kompletności Turinga; TC zapewnia tylko, że język może obliczyć żądaną funkcję, a nie, że może pokazać wynik. W praktyce każdy użyteczny język ma jakiś sposób na interakcję ze światem.

Z bardziej praktycznego punktu widzenia: jeśli możesz przetłumaczyć wszystkie programy w języku kompletnym Turinga na swój język, to (o ile wiem) Twój język musi być kompletny Turinga. Dlatego jeśli chcesz sprawdzić, czy język, który zaprojektowałeś, jest kompletny dla Turinga, możesz po prostu napisać Brainf *** do kompilatora YourLanguage i udowodnić / wykazać, że potrafi on skompilować wszystkie legalne programy BF.

Aby to wyjaśnić, mam na myśli, że oprócz interpretera języka YourLanguage, piszesz kompilator (w dowolnym języku), który może kompilować dowolny program BF do Twojego języka (oczywiście zachowując tę ​​samą semantykę).

System można uznać za kompletny Turinga tylko wtedy, gdy może on zrobić wszystko, co może zrobić uniwersalna maszyna Turinga. Ponieważ mówi się, że uniwersalna maszyna Turinga jest w stanie rozwiązać dowolną funkcję obliczeniową w danym czasie, kompletne systemy Turinga mogą również to zrobić.

Aby sprawdzić, czy coś jest zakończone, sprawdź, czy możesz zaimplementować w nim maszynę Turinga. Innymi słowy, sprawdź, czy może symulować:

1. Umiejętność odczytu i zapisu „zmiennych” (lub dowolnych danych) : Prawie oczywiste.
2. Zdolność do symulacji przesunięcia głowicy odczytu / zapisu : Nie wystarczy po prostu wyszukiwać i przechowywać zmienne. Musi być także możliwa symulacja zdolności poruszania głową taśmy w celu odniesienia do innych zmiennych. Można to często zasymulować w językach programowania przy użyciu struktur danych tablicowych (lub równoważnych) lub, w przypadku niektórych języków, takich jak kod maszynowy, możliwość odniesienia do innych zmiennych za pomocą „wskaźników” (lub równoważnych).
3. Zdolność do symulacji maszyny stanów skończonych : Chociaż nie jest to często wymieniane, maszyny Turinga są w rzeczywistości odmianą maszyn stanów skończonych często używanych w rozwoju AI. Alan Turing powiedział, że celem stanów jest symulacja „różnych sposobów rozwiązywania problemów”.
4. Stan „zatrzymania” : chociaż często wspomniany zestaw reguł musi być w stanie się powtarzać, aby uznać się za zakończony Turinga, nie jest to tak naprawdę dobre kryterium, ponieważ formalna definicja tego, czym jest algorytm, musi być zawsze ostatecznie zakończyć. Jeśli nie mogą zakończyć w jakiś sposób, oznacza to, że nie jest to ukończenie Turinga lub wspomniany algorytm nie jest funkcją obliczalną. Sprawdzanie kompletnych systemów, które technicznie nie mogą zakończyć się ze względu na sposób, w jaki działają (np. Konsole do gier), pozwala ominąć to ograniczenie, będąc w stanie w pewien sposób „symulować” stan zatrzymania. Nie mylić z „problemem zatrzymania”, niezdecydowaną funkcją, która to potwierdza ”

Są to prawdziwe minimalne wymagania dla systemu, który należy uznać za kompletny. Nic dodać nic ująć. Jeśli nie może symulować żadnego z nich w jakiś sposób, to nie jest to kompletny Turing. Metody proponowane przez innych ludzi są tylko środkiem do celu, ponieważ istnieje kilka kompletnych systemów Turinga, które nie mają tych funkcji.

Zauważ, że nie ma znanego sposobu na zbudowanie prawdziwego kompletnego systemu Turinga. Wynika to z faktu, że nie ma znanego sposobu na autentyczną symulację nieograniczonej taśmy maszyny Turinga w przestrzeni fizycznej.

Język programowania jest w pełni ukończony, jeśli możesz wykonać z nim jakiekolwiek obliczenia. Nie ma tylko jednego zestawu funkcji, który sprawia, że ​​turing jest kompletny, więc odpowiedzi mówiące, że potrzebujesz pętli lub że potrzebujesz zmiennych, są niepoprawne, ponieważ istnieją języki, które nie mają ani Turinga, ale są kompletne.

Alan Turing stworzył uniwersalną maszynę Turinga i jeśli możesz przetłumaczyć dowolny program zaprojektowany do pracy na uniwersalnej maszynie do pracy w Twoim języku, to również Turing jest kompletny. Działa to również pośrednio, dzięki czemu można powiedzieć, że język X jest w pełni ukończony, jeśli wszystkie programy do pełnego języka Y można przetłumaczyć na X, ponieważ wszystkie uniwersalne programy maszyny Turing można przetłumaczyć na program Y.

Złożoność czasowa, złożoność przestrzeni, łatwość formatu wejścia / wyjścia i łatwość pisania dowolnego programu nie są uwzględnione w równaniu, więc taka maszyna może teoretycznie wykonać wszystkie obliczenia, jeśli obliczenia nie zostaną zatrzymane przez utratę mocy lub połknięcie Ziemi przez słońce.

Zwykle, aby udowodnić kompletność Turinga, tworzą tłumacza dla każdego sprawdzonego języka Turinga kompletnego, ale do jego działania potrzebne są środki wejścia i wyjścia, dwie rzeczy, które tak naprawdę nie są wymagane, aby język był kompletny. Wystarczy, że Twój program może zmienić swój stan podczas uruchamiania i że możesz sprawdzić pamięć po zatrzymaniu programu.

Aby stworzyć udany język, potrzeba jednak czegoś więcej niż kompletności i jest to prawdą nawet w przypadku turingów. Nie sądzę, że BrainFuck byłby popularny bez ,i ..

Nie możesz powiedzieć, czy zapętli się w nieskończoność, czy przestanie.

-------------

Objaśnienie: Biorąc pod uwagę pewne dane wejściowe, nie można w każdym przypadku stwierdzić (za pomocą innej maszyny Turinga), czy rzecz zapętli się w nieskończoność, czy w końcu zatrzyma się, z wyjątkiem uruchomienia jej (co daje odpowiedź, jeśli się zatrzyma, ale nie jeśli się zapętli!).

Oznacza to, że musisz być w stanie w jakiś sposób przechowywać potencjalnie nieograniczoną ilość danych - musi istnieć odpowiednik nieskończonej taśmy, bez względu na to, jak skomplikowany! (W przeciwnym razie istnieje tylko skończona liczba stanów, a następnie możesz sprawdzić, czy przeszedłeś wcześniej ten stan i ostatecznie się zatrzymać). Ogólnie rzecz biorąc, maszyny Turinga mogą zwiększać lub zmniejszać rozmiar swojego stanu za pomocą kontrolowanych środków.

Ponieważ oryginalna uniwersalna maszyna Turinga ma nierozwiązywalny problem z zatrzymaniem, twoja kompletna maszyna Turing musi również mieć nierozwiązywalny problem z zatrzymaniem.

Systemy Turing complete mogą emulować dowolny inny system Turing complete, więc jeśli możesz zbudować emulator dla jakiegoś dobrze znanego systemu Turing complete w swoim systemie, to dowodzi, że twój system jest również Turing complete.

Załóżmy na przykład, że chcesz udowodnić, że Snakes & Ladders jest ukończony, biorąc pod uwagę planszę z nieskończenie powtarzającym się wzorem siatki (z inną wersją u góry i po lewej stronie). Wiedząc, że 2-licznikowa maszyna Minsky jest ukończona przez Turinga (która ma 2 nieograniczone liczniki i 1 stan z skończonej liczby), możesz zbudować równoważną tablicę, w której pozycja X i Y na siatce jest bieżącą wartością 2 liczników a bieżąca ścieżka to bieżący stan. Huk! Właśnie udowodniłeś, że Snakes & Ladders są kompletne.

Jednym z niezbędnych warunków jest pętla z maksymalną liczbą iteracji, która nie jest określona przed iteracją, lub rekurencja, w której maksymalna głębokość rekurencji nie jest określona z wyprzedzeniem. Na przykład dla ... w ... pętlach, które można znaleźć w wielu nowszych językach, nie wystarczy, aby język był kompletny (ale będą miały inne środki). Zauważ, że nie oznacza to ograniczonej liczby iteracji lub ograniczonej głębokości rekurencji, ale że maksymalne iteracje i głębokość rekurencji muszą być obliczone wcześniej.

Na przykład funkcja Ackermanna nie może być obliczona w języku bez tych funkcji. Z drugiej strony można napisać wiele bardzo skomplikowanych i bardzo przydatnych programów, które nie wymagają tych funkcji.

Z drugiej strony, przy każdym liczeniu iteracji i każdej obliczonej głębokości rekurencji nie tylko można zdecydować, czy program się zatrzyma, czy nie, ale również .

wiem, że nie jest to formalnie poprawna odpowiedź, ale kiedy wyjmiesz „minimum” z „Turing-complete” i przywrócisz „praktyczne” z powrotem tam, gdzie należy, zobaczysz najważniejsze cechy, które odróżniają język programowania od język znaczników to

• zmienne
• warunkowe (jeśli / to ...)
• pętla (pętla / przerwa, podczas gdy ...)

następny przyjdź

• funkcje anonimowe i nazwane

aby przetestować te twierdzenia, zacznij od języka znaczników, powiedzmy HTML. moglibyśmy wymyślić HTML + tylko ze zmiennymi lub tylko z warunkami warunkowymi (MS zrobił to z komentarzami warunkowymi), lub z jakąś konstrukcją pętli (która przy braku warunków warunkowych prawdopodobnie byłaby czymś podobnym <repeat n='4'>...</repeat>). wykonanie dowolnego z nich sprawi, że HTML + będzie znacznie (?) silniejszy niż zwykły HTML, ale nadal byłby bardziej znacznikiem niż językiem programowania; z każdą nową funkcją uczynisz ją mniej deklaratywnym, a bardziej imperatywnym językiem.

poszukiwanie minimalności w logice i programowaniu jest z pewnością ważne i interesujące, ale gdybym musiał nauczyć młodych lub starych „co to jest programowanie” i „jak nauczyć się programować”, nie zaczynałbym od pełnej szerokości i szerokości teoretycznych podstaw kompletności Turinga. cała esencja gotowania i programowania polega na robieniu rzeczy we właściwej kolejności, powtarzaniu do momentu przygotowania, tak jak zrobiła to twoja mama. to o mnie podsumowuje.

z drugiej strony nigdy nie skończyłem mojego CS.