Co sprawia, że język Turing jest kompletny?

A Turing tarpit to rodzaj ezoterycznego języka programowania, który stara się być kompletny według Turinga, używając jak najmniejszej liczby elementów. Brainfuck to chyba najbardziej znany tarpit, ale jest ich wiele.

• Iota i Jot to języki funkcjonalne z odpowiednio dwoma i trzema symbolami, oparte na SK (I) rachunek kombinatorowy .

• OISC ( Jeden komputer z zestawem instrukcji ) oznacza typ imperatywnego obliczenia, które wymaga tylko jednej instrukcji z jednym lub więcej argumentami, zwykle „odejmowanie i rozgałęzienie, jeśli jest mniejsze lub równe zero” lub „Odwróć, odejmij i pomiń, jeśli pożycz”. MMU x86 implementuje poprzednią instrukcję i dlatego jest kompletna w Turingu.

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

1. Forma warunkowego powtórzenia lub warunkowego skoku (np. while, if + goto)

2. Sposób czytania i zapisywania jakiejś formy przechowywania (np. , zmienne, taśma)

W przypadku rachunku lambda – językiem funkcyjnym opartym na TC, potrzeby:

1. Możliwość abstrakcji funkcji na argumentach (np. abstrakcji lambda, cudzysłowu)

2. Możliwość zastosowania funkcji do argumenty (np. redukcja)

Istnieją oczywiście inne sposoby patrzenia na obliczenia, ale są to typowe modele dla tarpitów Turinga. Zwróć uwagę, że prawdziwe komputery nie są uniwersalnymi maszynami Turinga , ponieważ nie mają nieograniczonej pamięci masowej. Ściśle mówiąc, są to „ograniczone maszyny magazynowe”. Jeśli miałbyś dodawać do nich pamięć, asymptotycznie zbliżałyby się do maszyn Turinga u władzy. Jednak nawet ograniczone maszyny magazynujące i maszyny o skończonych stanach są przydatne do obliczeń; po prostu nie są uniwersalne .

Ściśle mówiąc, I / O 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 interakcji ze światem.

Komentarze

• Czy proste zmienne są wystarczające w przypadku języków imperatywnych? Miałem wrażenie, że jakiś rodzaj zbioru (np. Tablic lub połączonych list) byłby potrzebny.
• @luiscubal musisz mieć możliwość określenia dowolnej ilości danych. Za pomocą prostych zmiennych możesz przedstawić ilość danych, które mają same zmienne. A co, jeśli musisz przedstawić N + 1 różnych fragmentów danych. Można by argumentować, że dzięki sztuczkom , takim jak gra Fractran, można to zrobić nawet w prostych zmiennych … ale ' nie do końca to, o co prosisz '.
• Isn ' t wymaga, aby język obsługiwał NIEKOŃCZĄCE SIĘ pętle?
• Re, ” każdy przydatny język ma sposób interakcji ze światem. ” Algol 60 nie miał żadnego zdefiniowanego sposobu interakcji ze światem. Wszystkie twoje wejścia / wyjścia w programie Algol 60 zostały wykonane przez wywołanie funkcji bibliotecznych, a funkcje biblioteki mogą być zupełnie inne w różnych implementacjach. Ale niniejszym wycofuję się z dyskusji na temat tego, czy Algol 60 był ” użyteczny. ”

Z bardziej praktycznego punktu widzenia: jeśli możesz przetłumaczyć wszystkie programy w języku Turinga na swój język, to (o ile Wiem), twój język musi być kompletny w języku Turinga.Dlatego, jeśli chcesz sprawdzić, czy zaprojektowany język jest kompletny w języku Turing, możesz po prostu napisać Brainf *** do kompilatora YourLanguage i udowodnić / zademonstrować, że może kompilować wszystkie legalne programy BF.

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

Komentarze

• Tak, z pewnością byłby to najbardziej praktyczny sposób podejścia. </sarcasm>
• @RobertHarvey ma rację, ale ogólny pomysł jest bardzo istotny. Udowodniono, że Brainfuck jest kompletny i bardzo prosty, jak na języki programowania. W przypadku nie-ezoterycznych języków programowania zaimplementowanie interpretera typu brainfuck może być znacznie łatwiejsze i szybsze niż podawanie dokładnego dowodu znikąd (mogę zaimplementować BF w kilku wierszach Pythona, ale ' nie jestem pewien, od czego zacząć od formalnego dowodu, że Python jest kompletny); a dziesiątki ezoterycznych języków zainspirowanych mózgiem mózgów są znane jako kompletne, ponieważ ' wiemy, jak mapują się na brainfuck.
• @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, a w przeciwnym razie znaleźć odpowiedni inny język).
• @delnan: zrobisz musisz jednak udowodnić, że twój interpreter BF poprawnie implementuje specyfikację BF, IOW będziesz musiał udowodnić, że twój interpreter BF jest w rzeczywistości tłumaczem BF, a nie tłumaczem języka podobnego do BF, który może, ale nie musi być Turing-complete.
• @ DarekNędza, że ' jest po prostu naturalną konsekwencją tego, jak definiowana jest kompletność Turinga; każde rozszerzenie języka Turing Complete nadal będzie Turing Complete.

System można uznać tylko za być kompletnym Turingiem, jeśli może zrobić wszystko, co może zrobić uniwersalna maszyna Turinga. Ponieważ mówi się, że uniwersalna maszyna Turinga jest w stanie rozwiązać dowolną obliczalną funkcję w określonym czasie, kompletne systemy Turinga również mogą to robić.

Aby sprawdzić, czy coś jest kompletne, zobacz, czy może zaimplementować w sobie maszynę Turinga. Innymi słowy, sprawdź, czy może symulować następujące elementy:

1. Możliwość odczytu i zapisu „zmiennych” (lub dowolnych danych) : dość oczywiste.
2. Możliwość symulacji ruchu głowicy odczytu / zapisu : Nie wystarczy po prostu pobierać i przechowywać zmienne. Musi być również możliwa symulacja zdolności poruszania głową taśmy w celu odniesienia się do innych zmiennych. Często można to symulować w językach programowania przy użyciu tablicowych struktur danych (lub równoważnych) lub, w przypadku niektórych języków, takich jak kod maszynowy, możliwość odwoływania się do innych zmiennych za pomocą „wskaźników” (lub równoważnych).
3. Możliwość symulacji automatu skończonego : Chociaż nie jest to często wspominane, maszyny Turinga są w rzeczywistości odmiana maszyn skończonych często używanych w rozwoju sztucznej inteligencji. Alan Turing powiedział, że celem stanów jest symulacja „różnych trybów rozwiązywania problemów” danej osoby.
4. Stan „zatrzymania” : Chociaż często wspomina się, że zestaw reguł musi się powtarzać, aby można było uznać go za kompletny Turinga, nie jest to naprawdę dobre kryterium, ponieważ formalna definicja tego, co Algorytm to algorytm stanu, który zawsze musi ostatecznie zakończyć. Jeśli nie mogą w jakiś sposób dojść do wniosku, albo nie jest on ukończony, albo wspomniany algorytm nie jest funkcją obliczeniową. Turing kompletnych systemów, które technicznie nie mogą zostać zakończone ze względu na sposób działania (na przykład konsole do gier), omijają to ograniczenie, będąc w stanie w jakiś sposób „symulować” stan zatrzymania. Nie należy ich mylić z „problemem zatrzymania” „, nierozstrzygalna funkcja, która udowadnia, że nie da się zbudować systemu, który mógłby wykryć ze 100% niezawodnością, czy dane wejście spowoduje, że inny system nie zakończy działania.

To są prawdziwe minimum wymagania dotyczące systemu, który należy uznać za kompletny w Turingu. Nic dodać nic ująć. Jeśli nie może w jakiś sposób zasymulować żadnego z nich, to nie jest ukończone. Metody proponowane przez innych ludzi są jedynie środkami do końca, ponieważ istnieje kilka kompletnych systemów Turing, które nie mają tych cech.

Zauważ, że nie ma znanego sposobu na zbudowanie prawdziwego kompletnego systemu Turing . Dzieje się tak, ponieważ „nie ma znanego sposobu, aby autentycznie zasymulować nieograniczoność taśmy maszyny Turinga w przestrzeni fizycznej.

Język programowania jest kompletny, jeśli można na nim wykonać jakiekolwiek obliczenia.Nie ma tylko jednego zestawu funkcji, który zapewnia kompletność języka, więc odpowiedzi mówiące, że potrzebujesz pętli lub zmiennych, są błędne, ponieważ istnieją języki, których nie ma ale turing jest kompletny.

Alan Turing stworzył uniwersalną maszynę do turinga i jeśli potrafisz przetłumaczyć dowolny program zaprojektowany do pracy na tej uniwersalnej maszynie na Twój język, to również Turing jest kompletny. Działa to również pośrednio, więc możesz powiedzieć, że język X jest kompletny, jeśli wszystkie programy do uczenia pełnego języka Y mogą być przetłumaczone na X, ponieważ wszystkie uniwersalne programy maszyny turinga można przetłumaczyć na program Y.

Złożoność czasowa , złożoność przestrzeni, łatwy format wejścia / wyjścia i łatwy do napisania żaden program nie jest uwzględniony 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, co udowodniono, że jest kompletnym językiem, ale aby działał, potrzebujesz środków wejściowych i wyjściowych, dwóch rzeczy, które tak naprawdę nie są wymagane, aby język był kompletny. Wystarczy, że Twój program może zmienić swój stan przy starcie i możesz sprawdzić pamięć po jego zatrzymaniu.

Jednak aby stworzyć udany język, potrzeba czegoś więcej niż tylko kompletności. prawdziwe nawet dla plandek. Nie sądzę, aby BrainFuck byłby popularny bez , i ..

Komentarze

• ” Język programowania jest gotowy, jeśli możesz wykonać jakiekolwiek obliczenia z nim. ” To ' to teza Kościoła Turinga, a nie to, co sprawia, że język Turinga jest kompletny.
• @Rhymoid Więc masz na myśli, że nic nie jest kompletne, jeśli nie możesz zrobić interpretatora? Tj. Rachunek lambda nie jest kompletny, nawet jeśli ' jest równy?
• I ' wciąż szukam autorytatywnej definicji terminów odpowiednik Turinga i Turing-complete (i Turing-potężny). I ' widzieliśmy już zbyt wiele przypadków, od ludzi na forach dyskusyjnych po badaczy w ich własnych pieprzonych ' artykułach, którzy inaczej interpretują te terminy.
• W każdym razie, Interpretuję ' Turing-complete ' jako symulację równoważną Universal Turing Machine (UTM; który z kolei może symulować dowolną maszynę Turinga – stąd ' uniwersalny '). W artykule Turinga ' z 1936 r., W którym przedstawił swoje maszyny, zdefiniował pojęcie UTM i przedstawił szkic dowodu, że UTM są równoważne symulacji Church ' rachunek lambda s. W ten sposób udowodnił, że mają taką samą moc obliczeniową. Teza Church-Turinga stwierdza, po prostu, że ” ' to cała moc obliczeniowa, jaką ' zawsze otrzymamy „.
• Ma dwie formalne definicje dla strony Turing poświęconej kompletności Wikipedii . Jeden wymaga I / O, a drugi nie ' t. Ten, który ' nie mówi, że maszyna jest w trakcie ukończenia, jeśli może obliczyć każdą obliczalną funkcję Turinga. To sprawia, że rachunek lambda z powrotem jest kompletny, ponieważ w rachunku lambda można łatwo utworzyć równy program, który oblicza to samo, co inne programy maszyny turinga.

Nie można powiedzieć, czy będzie to nieskończona pętla, czy też zatrzymanie.

————-

Wyjaśnienie: Biorąc pod uwagę pewne dane wejściowe, nie można powiedzieć w każdym przypadku (używając innej maszyny Turinga), czy coś będzie się zapętlać w nieskończoność, czy w końcu się zatrzyma, z wyjątkiem uruchomienia go (co daje odpowiedź, jeśli tak się stanie stop, 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 zawiłe! (W przeciwnym razie istnieje tylko skończona liczba stanów, a następnie możesz sprawdzić, czy wcześniej przeszedłeś przez ten stan i ostatecznie się zatrzymałeś). Ogólnie rzecz biorąc, maszyny Turinga mogą zwiększać lub zmniejszać rozmiar swojego stanu za pomocą pewnych kontrolowanych środków.

Ponieważ oryginalna uniwersalna maszyna Turinga ma nierozwiązywalny problem z zatrzymaniem, twoja własna kompletna maszyna Turinga również musi mieć nierozwiązywalne zatrzymanie problem.

Kompletne systemy Turing mogą emulować każdy inny kompletny system Turing, więc jeśli możesz zbudować emulator dla jakiegoś dobrze znanego kompletnego systemu Turing w swoim systemie, to udowodni, że Twój system jest również kompletny.

Na przykład przypuśćmy, że chcesz udowodnić, że Węże & Drabiny są kompletne, mając tablicę z nieskończenie powtarzającym się wzorem siatki (z inną wersją na górze i lewa strona). Wiedząc, że 2-licznikowa maszyna Minskyego jest kompletna 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 stan obecny. Huk! Właśnie udowodniłeś, że Węże & Drabiny są ukończone.

Komentarze

• Nie ' t kup ten argument. To, że problem zatrzymania jest nierozstrzygalny dla maszyn Turinga, nie oznacza bezpośrednio, że każda notacja, która pozwala na określenie programu, dla którego problem zatrzymania jest nierozstrzygalny, jest kompletna. Tylko odwrotność jest oczywiście prawdziwa: jeśli notacja jest kompletna w Turingu, to oczywiście możliwe jest napisanie programów, dla których problem zatrzymania jest nierozstrzygalny.
• It ' jest warunkiem koniecznym. Jeśli możesz zdecydować o zatrzymaniu każdego programu, język nie jest ' t Turing zakończony.

Jednym warunkiem koniecznym jest pętla z maksymalną liczbą iteracji, która nie jest określona przed iteracją, lub rekurencja, w której maksymalna głębokość rekursji nie jest określana z wyprzedzeniem. Na przykład pętle … in …, jakie można znaleźć w wielu nowszych językach, nie są wystarczające, aby uzupełnić język turinga (ale będą miały inne sposoby). Zauważ, że nie oznacza to ograniczonej liczby iteracji lub ograniczonej głębokości rekurencji, ale że maksymalna iteracja i głębokość rekurencji muszą być obliczane z wyprzedzeniem.

Na przykład funkcja Ackermanna nie może być obliczona w języku bez te funkcje. Z drugiej strony można napisać wiele bardzo złożonych i bardzo przydatnych programów bez konieczności korzystania z tych funkcji.

Z drugiej strony, z każdą liczbą iteracji i każdą głębokością rekurencji obliczaną z wyprzedzeniem, nie tylko czy można zdecydować, czy program się zatrzyma, czy nie, ale będzie zatrzymany.

Wiem, że to nie jest poprawna formalnie odpowiedź, ale kiedy wyjmiesz „minimum” z „Turing-Complete” i umieścisz „praktyczne” z powrotem tam, gdzie powinno, zobaczysz najważniejsze cechy, które odróżniają język programowania od językiem znaczników są

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

następna com e

• 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 warunkami warunkowymi (firma MS zrobiła to z komentarzami warunkowymi) lub jakąś konstrukcją pętli (która w przypadku braku warunków warunkowych prawdopodobnie skończyłaby się na czymś takim jak <repeat n="4">...</repeat>). zrobienie któregokolwiek z nich sprawi, że HTML + będzie znacznie (?) potężniejszy niż zwykły HTML, ale nadal będzie to bardziej znacznik niż język programowania; z każdą nową funkcją sprawiasz, że jest on mniej deklaratywny, a bardziej imperatywny.

poszukiwanie minimalności w logice i programowaniu jest z pewnością ważne i interesujące, ale gdybym musiał uczyć n00bies młodszych lub starszych „co to jest programowanie” i „jak nauczyć się programować”, trudno bym zacząć z całą szerokością i szerokością teoretycznych podstaw kompletności Turinga. Cała istota gotowania i programowania polega na robieniu rzeczy we właściwej kolejności, powtarzaniu, aż będzie gotowe, tak jak zrobiła to twoja mama. to podsumowuje dla mnie.

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

Komentarze

• Jeśli nie jesteś pewien, powinieneś najpierw to sprawdzić. fractran jest zakończony , podobnie jak brainf * ck . Zwróć również uwagę, że html 5 + CSS 3 jest ukończony w Turingu, ponieważ może zaimplementować reguła 110 .
• tak tak tak, wiem, ale wszystkie podane przykłady są mniej lub bardziej ezoteryczne (chociaż mogą być interesujące lub zaskakujące), m y odpowiedź była pragmatyczna i prawdopodobnie wcale nie była minimalna. Myślę, że ' jest ważne, aby to podkreślić – ta strona była numerem 1 podczas wyszukiwania kompletności Turinga w Google, odpowiedzi tutaj to IMHO mało przydatne dla, powiedzmy, n00bie kto chce wiedzieć, co odróżnia HTML od PHP lub Pythona. mam na myśli, że brainf ck nie nazywa się brainf ck bez powodu.