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

79

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

Ciekawy kot
źródło
21
Czy nie byłoby lepiej po prostu google go? en.wikipedia.org/wiki/Turing_completeness
aml90
2
Cześć Curious Cat, witamy w Programistach! Zaproszenia do list nie są tutaj na temat: usunąłem tę część z twojego pytania. To powiedziawszy, to zadanie jest bardzo szerokie: czy istnieje jakiś konkretny problem, nad którym pracujesz, a który myśli o kompletności Turinga?
3
@amalantony: Tak jak przypis .
Bobby,
Perspektywa informatyki znajduje się tutaj .
Raphael

Odpowiedzi:

73

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 nieuniwersalnymi 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.

Jon Purdy
źródło
Czy w przypadku języków rozkazujących wystarczy proste zmienne? Miałem wrażenie, że jakiś zbiór (np. Tablice lub powiązane listy) będzie potrzebny.
luiscubal
1
@luiscubal musisz być w stanie określić dowolną ilość danych. Za pomocą prostych zmiennych możesz reprezentować ilość danych, które same zmienne mają. Co jeśli musisz reprezentować N + 1 różnych fragmentów danych. Można argumentować, że przy sztuczkach takich jak Fractran można to zrobić nawet w prostych zmiennych ... ale nie o to pytasz.
Czy to nie jest wymagane, że język musi obsługiwać pętle ENDLESS ?
sergiol
Re „każdy przydatny język ma sposób na interakcję ze światem”. Algol 60 nie miał określonego sposobu interakcji ze światem. Wszystkie twoje operacje we / wy w programie Algol 60 zostały wykonane przez wywołanie funkcji bibliotecznych, a funkcje biblioteczne mogą być zupełnie inne w różnych implementacjach. Ale niniejszym wycofuję się z dyskusji na temat tego, czy Algol 60 był „przydatny”.
Solomon Slow
15

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ę).

Anton Golov
źródło
11
Tak, zdecydowanie byłby to najbardziej praktyczny sposób podejścia do tego. </sarcasm>
Robert Harvey
13
@RobertHarvey ma rację, ale ogólna idea jest bardzo ważna. Udowodniono, że Brainfuck jest kompletny i bardzo prosty w miarę rozwoju języków programowania. W przypadku nieezoterycznych języków programowania implementacja interpretera pieprzenia mózgu może być znacznie łatwiejsza i szybsza niż dostarczenie rygorystycznego dowodu znikąd (mogę zaimplementować BF w kilku wierszach Pythona, ale nie jestem pewien, od czego zacząć od formalnego dowód, że Python jest zakończony); a dziesiątki ezoterycznych języków inspirowanych pieprzeniem mózgu są kompletnie kompletne, ponieważ wiadomo, w jaki sposób mapują się one na pieprzenie mózgu.
7
@RobertHarvey: Dlaczego nie? Z pewnością ktoś projektujący swój własny język byłby w stanie napisać do niego kompilator BF (gdyby to było konieczne, i w innym przypadku znalazłby odpowiedni inny język).
Anton Golov
5
@delnan: Ty będziesz musiał udowodnić jednak, że BF interpreter poprawnie implementuje specyfikację BF, IOW będzie musiał udowodnić, że BF interpreter jest w rzeczywistości, interpreter BF i nie interpreterem języka BF-tak może, ale nie musi, być kompletny w Turinga.
Jörg W Mittag
2
@ DarekNędza, to tylko naturalna konsekwencja definicji Turinga; każde rozszerzenie języka Turing Complete nadal będzie Turing Complete.
Anton Golov
8

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.

użytkownik3067516
źródło
4

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 ..

Sylwester
źródło
2
„Język programowania jest w pełni ukończony, jeśli możesz wykonać z nim jakiekolwiek obliczenia”. To teza Kościoła-Turinga, a nie to, co sprawia, że ​​język jest kompletny.
Rhymoid
@ Rhymoid Więc masz na myśli, że nic nie jest kompletne, chyba że możesz zrobić tłumacza? To znaczy. rachunek lambda nie jest kompletny, nawet jeśli jest równy?
Sylwester
1
Nadal szukam autorytatywnej definicji terminów Turing-ekwiwalent i Turing-zupełny (i Turing-potężny). Widziałem już zbyt wiele przypadków, od osób na forach dyskusyjnych po badaczy we własnych, cholernych artykułach, którzy interpretują te terminy w różny sposób.
Rhymoid
W każdym razie interpretuję „Turing-complete” jako symulację równoważną z uniwersalną maszyną Turinga (UTM; która z kolei jest w stanie symulować dowolną maszynę Turinga - stąd „uniwersalną”). W artykule Turinga z 1936 r., W którym przedstawił swoje maszyny, zdefiniował pojęcie UTM i dał szkic dowodu, że UTM są symulacją równoważną rachunkowi lambda Kościoła. W ten sposób udowodnił, że mają taką samą moc obliczeniową. Teza Turinga twierdzi, mówiąc prosto, że „to cała moc obliczeniowa, jaką kiedykolwiek dostaniesz”.
Rhymoid
Ma dwie formalne definicje strony kompletności Turinga w Wikipedii . Jedno wymaga wejścia / wyjścia, a drugie nie. Ten, który nie mówi, że maszyna jest gotowa, jeśli może obliczyć każdą funkcję obliczalną Turinga. Powoduje to, że rachunek lambda wraca do stanu pełnego ukończenia Turinga, ponieważ można łatwo stworzyć równy program w rachunku lambda, który oblicza to samo, co dowolne programy maszyny Turinga.
Sylwester
4

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.

Hubert Lamontagne
źródło
1
Nie kupuję tego argumentu. To, że problem zatrzymania jest nierozstrzygalny dla maszyn Turinga, nie oznacza bezpośrednio, że każda notacja, która pozwala określić program, dla którego problem zatrzymania jest nierozstrzygalny, jest zakończona. Jedynie odwrotność jest oczywiście prawdziwa: jeśli notacja jest zakończona według Turinga, wówczas oczywiście można pisać programy, dla których problem zatrzymania jest nierozstrzygalny.
5gon12eder
To warunek konieczny. Jeśli możesz zdecydować dla każdego programu, czy się zatrzyma, to język nie jest kompletny.
gnasher729,
4

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ż .

gnasher729
źródło
-1

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.

pływ
źródło
2
Jeśli nie jesteś pewien, powinieneś to najpierw zbadać. Fractran jest w pełni ukończony , podobnie jak brainf * ck . Zauważ też, że HTML 5 + CSS 3 jest Turing zakończony, ponieważ może implementować regułę 110 .
1
tak tak tak wiem ale wszystkie podane przykłady są mniej lub bardziej ezoteryczne (choć może interesujące lub zaskakujące), moja odpowiedź była pragmatyczna i prawdopodobnie wcale nie minimalna. myślę, że ważne jest, aby to zaznaczyć - ta strona była na pierwszym miejscu podczas wyszukiwania kompletności Turinga w Google. Odpowiedzi tutaj są IMHO mało przydatne, powiedzmy, n00bie, która chce wiedzieć, co odróżnia HTML od PHP lub Pythona. mam na myśli, że brainf ck nie jest nazywane brainf ck bez powodu.
przepływ