Widzę, że większość definicji tego, co ma być Turing-zupełne, jest do pewnego stopnia tautologiczna. Na przykład, jeśli Google „co oznacza bycie kompletnym Turinga”, otrzymuje:

Komputer jest kompletny, jeśli może rozwiązać każdy problem, który maszyna Turinga może ...

Chociaż jest bardzo dobrze określone, czy różne systemy są Turinga kompletne, czy nie, nie widziałem wyjaśnienia, jakie są implikacje / konsekwencje bycia Turingiem kompletnym.

Co może zrobić maszyna Turinga, jeśli nie ma maszyny innej niż Turing, która mogłaby wykonać to samo zadanie? Na przykład komputer może wykonywać proste obliczenia, takie jak (1+5)/3=?, ale zwykły kalkulator może je również wykonywać, co nie jest kompletne, jeśli mam rację.

Czy istnieje sposób na zdefiniowanie możliwości maszyny Turinga, nie mówiąc tylko „o możliwości symulacji innej maszyny Turinga”?

Zastanawiałem się przez chwilę, czy dodać jeszcze jedną odpowiedź. Pozostałe odpowiedzi koncentrują się na środku jego pytania (o „całkowitym turingu”, „tautologii” i tak dalej). Pozwól mi uchwycić pierwszą i ostatnią część, a zatem większy i nieco filozoficzny obraz:

Ale co to oznacza?

Co oznacza bycie kompletnym Turinga?

Czy istnieje sposób na zdefiniowanie możliwości maszyny Turinga, nie mówiąc tylko „o możliwości symulacji innej maszyny Turinga”?

Mówiąc nieformalnie, bycie Turingem kompletnym oznacza, że ​​Twój mechanizm może uruchomić dowolny algorytm, o którym możesz pomyśleć, bez względu na to, jak skomplikowany, głęboki, rekurencyjny, skomplikowany, długi (pod względem kodu) i bez względu na to, ile miejsca lub czasu by to zajmowało potrzebne do oceny. Jest rzeczą oczywistą, że tylko udaje, czy problem jest obliczalny, ale jeśli to jest obliczalny, to będzie sukces (halt).

(Uwaga: aby dowiedzieć się, dlaczego jest to „nieformalne”, zapoznaj się z tezą Kościoła Turinga, która idzie w tym kierunku, z bardziej złożonym brzmieniem; będąc tezą, może być lub nie może być poprawna. Dzięki @DavidRicherby za wskazując to małe pominięcie w komentarzu).

„Algorytm” oznacza to, co dzisiaj powszechnie rozumiemy jako algorytm komputerowy; tj. szereg dyskretnych kroków manipulujących pamięcią, z domieszką pewnej logiki sterowania. Nie jest jednak podobny do maszyny Oracle, tzn. nie może „zgadnąć”.

Przykład praktycznego języka innego niż tc

Jeśli sam się zaprogramowałeś, prawdopodobnie znasz wyrażenia regularne, używane do dopasowania ciągów znaków do jakiegoś wzorca.

To jest jeden przykład konstrukcji, która nie jest ukończona przez Turinga. Możesz łatwo znaleźć ćwiczenia, w których niemożliwe jest utworzenie wyrażenia regularnego pasującego do określonych fraz.

Na przykład (a to z pewnością drażni wielu programistów w rzeczywistych rzeczywistych aplikacjach), teoretycznie i praktycznie niemożliwe jest utworzenie wyrażenia regularnego pasującego do języka programowania lub dokumentu XML: wyrażenie regularne nie może znaleźć struktury bloku ( do ... endlub { ... }w językach; otwieranie i zamykanie znaczników w dokumentach XML), jeśli dopuszcza się ich dowolną głębokość. Jeśli istnieje limit, na przykład możesz mieć tylko 3 poziomy „rekurencji”, możesz znaleźć wyrażenie regularne; ale jeśli nie jest to ograniczone, to nie da się.

Ponieważ jest oczywiście możliwe stworzenie programu w języku kompletnym Turinga (jak C) do parsowania kodu źródłowego (robi to dowolny kompilator), wyrażenia regularne nigdy nie będą w stanie symulować tego programu, dlatego z definicji nie są kompletne Turinga

Motywacja

Sam pomysł maszyny Turinga nie jest niczym praktycznym; tzn. Turing z pewnością nie wynalazł go, aby stworzyć prawdziwy komputer lub coś takiego, w przeciwieństwie na przykład do Charlesa Babbage'a lub von Neumanna. Koncepcja maszyny Turinga jest niezwykle prosta. Składa się prawie z niczego. Redukuje liczbę możliwych (i rzeczywistych) komputerów do najgorszego możliwego do wyobrażenia minimum.

Z kolei to uproszczenie polega na tym, że ułatwia to (ish) zastanawianie się nad pytaniami teoretycznymi (takimi jak zatrzymanie problemów, klasy złożoności i cokolwiek, na co przeszkadza sobie informatyka teoretyczna). Jedną z cech jest w szczególności to, że zazwyczaj bardzo łatwo jest zweryfikować, czy dany język lub komputer może symulować Maszynę Turinga, po prostu programując maszynę Turinga (która jest taka łatwa!) W tym języku.

Do nieskończoności

Pamiętaj, że nigdy nie potrzebujesz nieskończonego czasu lub pamięci; ale zarówno czas, jak i pamięć są nieograniczone. Będą miały maksymalną wartość dla każdego pojedynczego obliczalnego przebiegu, ale nie ma ograniczenia, jak duża może być ta wartość. Fakt, że w prawdziwym komputerze ostatecznie zabraknie pamięci RAM, został tutaj opisany; jest to oczywiście ograniczenie dla dowolnego komputera fizycznego, ale jest również oczywiste i nie interesuje teoretycznej „mocy obliczeniowej” maszyny. Nie jesteśmy też wcale zainteresowani tym, ile to faktycznie zajmuje. Dzięki temu nasza mała maszyna może wykorzystywać dowolną ilość czasu i przestrzeni, co czyni ją absolutnie niepraktyczną.

... i nie tylko

Jeden zdumiewający ostatni punkt, to jest to, że takie proste, proste rzeczy można zrobić wszystko, każdy wyobrażalny prawdziwy komputer może nigdy , w całym wszechświecie, osiągnąć (po prostu bardzo dużo wolniej) - co najmniej tak daleko jak wiemy dzisiaj.

To wcale nie jest tautologiczne.

Model obliczeniowy jest kompletny Turinga, jeśli może symulować wszystkie maszyny Turinga, tj. Jest co najmniej tak samo wydajny jak maszyny Turinga.

Jedną rzeczą, którą mogą zrobić maszyny Turinga, jest symulacja innych maszyn Turinga (za pośrednictwem uniwersalnej maszyny Turinga). Oznacza to, że jeśli twój model obliczeniowy nie może symulować maszyn Turinga, nie może zrobić co najmniej jednej rzeczy, którą mogą zrobić maszyny Turinga, więc nie spełnia definicji, więc nie jest kompletny. Nie ma okrągłości, ponieważ nie zdefiniowaliśmy kompletności Turinga w kategoriach samej siebie: powiedzieliśmy, że kompletność Turinga jest właściwością robienia wszystkiego, co potrafią maszyny Turinga.

$a$$b$

Czy istnieje sposób na zdefiniowanie możliwości maszyny Turinga, nie mówiąc tylko „o możliwości symulacji innej maszyny Turinga”?

Nie jestem pewien, co rozumiesz przez „zdefiniowanie możliwości maszyn Turinga”. Możliwości są zdefiniowane w kategoriach automatów skończonych działających na nieskończonej taśmie. (Nie powtórzę pełnej definicji, ale można ją znaleźć np. Na Wikipedii ).

Model obliczeniowy Turinga jest tylko jednym z wielu równoważnych modeli obliczeniowych. Ma tę samą moc, co funkcje rekurencyjne Gödela i rachunek lambda Kościoła, które zostały zaproponowane w tym samym czasie, a także inne modele, takie jak wskaźnik. Dlatego możesz to stwierdzić

Komputer jest kompletny Turinga, jeśli może rozwiązać każdy problem, który potrafi Excel.

Działa to, ponieważ Excel jest również kompletny w Turingu. Polecam zajrzeć na stronę Wikipedii poświęconą tezie Church-Turinga oraz artykuł przeglądowy Blassa i Gurewicza „ Algorytmy: poszukiwanie absolutnych definicji” .

Jeśli chodzi o twoje pytanie, co może zrobić maszyna Turinga, czego nie potrafi maszyna nieobsługująca Turinga, na ogół odpowiedź niestety zależy od maszyny nieobsługującej Turinga.

Możliwe jest jednak zdefiniowanie nietrywialnych pojęć dotyczących problemów Turinga, na przykład:

$L$$A$$f$$a \in A$$f(a) \in L$

Zgodnie z tą definicją odpowiednie kodowanie problemu zatrzymania jest kompletne Turinga, a więc dla rozsądnej klasy maszyn (w zależności od definicji „wydajnie obliczalnego”), maszyna jest kompletna Turinga i może zrealizować niektóre (równoważnie wszystkie ) Pełny język Turinga.

Istnieje wiele innych kompletnych problemów Turinga uchwyconych przez ten formalizm, w zależności od definicji „wydajnie obliczalnego”, takich jak problem korespondencji Turinga oraz problemy dotyczące płytek Wanga i Gry Życia. Każdy z tych problemów może działać jako punkt odniesienia zamiast problemu zatrzymania.

Przede wszystkim pragnę zaznaczyć, że definicja kompletności Turinga wcale nie jest tautologiczna. Nie tylko udowadnianie modelu obliczeniowego Turing-complete jest interesującym rezultatem samym w sobie, ale umożliwia także natychmiastowe rozszerzenie wszystkich wyników teorii obliczeń na ten inny model obliczeniowy; na przykład: maszyny 2-licznikowe są kompletne Turinga, maszyny Turinga nie mogą rozwiązać problemu zatrzymania, dlatego żadne maszyny 2-licznikowe nie mogą.

Prostą charakterystykę funkcji obliczalnych przez maszynę Turinga podaje $\mu$- funkcje rekurencyjne, minimalny zestaw funkcji zamkniętych w składzie, prymitywny operator rekurencji i minimalizacji, który zawiera funkcję stale zerową, tożsamość i funkcję następcy.

Taka klasa zawiera funkcje, które są „intuicyjnie obliczalne”, to znaczy obliczenia, które człowiek mógłby wykonać na podstawie precyzyjnego algorytmu ołówkiem i papierem.

Oczywiście „intuicyjnie obliczalne” nie jest tak naprawdę formalną definicją, identyfikacja „intuicyjnie obliczalnej” z „obliczeniem Turinga” jest znana jako teza Kościoła. Ponieważ wiele formalnych prób scharakteryzowania obliczalności ostatecznie zbiega się z modelem obliczeniowym, który jest kompletny według Turinga, chociaż nigdy nie będzie formalnego dowodu takiego twierdzenia w sensie matematycznym, istnieją poważne powody, by w to wierzyć.

Maszyna Turinga może obliczyć ten sam zestaw funkcji co uniwersalny komputer kwantowy, który może symulować dowolny układ fizyczny:

https://www.cs.princeton.edu/courses/archive/fall04/cos576/papers/deutsch85.pdf

Jako taka, maszyna Turinga jest w stanie wykonać dowolne przetwarzanie informacji dozwolone przez prawa fizyki, chociaż nie zawsze będzie przetwarzać takie informacje tak skutecznie, jak to możliwe.