Niedawno usłyszałem ciekawą analogię, która stwierdza, że ​​dowód Turinga na nierozstrzygalność problemu zatrzymania jest bardzo podobny do paradoksu fryzjerskiego Russella.

Zastanawiałem się więc: matematycy w końcu zdołali ujednolicić teorię zbiorów, przechodząc od naiwnego sformułowania pola przez Cantora do bardziej złożonego systemu aksjomatów (teoria zbiorów ZFC), dokonując po drodze istotnych wyłączeń (ograniczeń) i dodatków.

Czy może byłoby zatem możliwe wymyślenie abstrakcyjnego opisu ogólnego obliczenia, który jest mocniejszy i bardziej wyrazisty niż maszyny Turinga i za pomocą którego można uzyskać dowód egzystencjalny, a może nawet algorytm rozwiązania problemu zatrzymania dowolna maszyna Turinga?

Naprawdę nie można porównywać. Naiwna teoria zbiorów miała paradoksy, które zostały wyeliminowane przez teorię zbiorów ZFC. Teorię należy ulepszyć w celu zapewnienia spójności, ponieważ podstawowym założeniem prac naukowych jest to, że spójność jest osiągalna (w przeciwnym razie rozumowanie stanie się przypadkowym biznesem). Przypuszczam, że matematycy oczekiwali, że to będzie możliwe, i pracowali nad rozwiązaniem tego problemu.

Nie ma takiej sytuacji z teorią obliczeń i problemem zatrzymania. Nie ma paradoksu, nie ma niekonsekwencji. Tak się składa, że ​​nie ma maszyny Turinga, która rozwiązałaby problem zatrzymania TM. To po prostu twierdzenie, a nie paradoks.

Być może więc jakiś przełom w naszym zrozumieniu wszechświata doprowadzi do modeli obliczeniowych wykraczających poza to, co możemy sobie teraz wyobrazić. Jedynym takim zdarzeniem, w bardzo słabej formie, które pozostaje w sferze TM, było prawdopodobnie przetwarzanie kwantowe. Poza tym bardzo słabym przykładem, który dotyka złożoności (jak długo to zajmuje?), A nie obliczalności (czy jest to wykonalne?), Wątpię, czy ktokolwiek na tej planecie ma pojęcie, że należy oczekiwać obliczalności wykraczającej poza TM.

Ponadto problem zatrzymania jest bezpośrednią konsekwencją tego, że maszyny Turinga można opisać skończonym fragmentem tekstu, sekwencją symboli. Dotyczy to w rzeczywistości całej naszej wiedzy (o ile wiemy) i właśnie dlatego mowa i książki są tak ważne. Dotyczy to wszystkich naszych technik opisywania dowodów i obliczeń.

Więc nawet gdybyśmy znaleźli sposób na rozszerzenie sposobu obliczania, powiedzmy za pomocą maszyn T +. Albo oznaczałoby to, że znaleźliśmy sposób wyrażania wiedzy poza pisaniem skończonego dokumentu, w którym to przypadku cała sprawa nie wchodzi w zakres mojej jurysdykcji (twierdzę, że jest absolutną niekompetencją) i prawdopodobnie kogoś innego. Lub nadal byłby możliwy do wyrażenia w skończonych dokumentach, w takim przypadku miałby swój własny problem zatrzymania dla maszyn T +. I znowu zadajesz to pytanie.

W rzeczywistości taka sytuacja istnieje odwrotnie. Niektóre typy maszyn są słabsze niż maszyny Turinga, takie jak automaty liniowe (LBA). Są jednak dość potężne, ale można pokazać dokładnie tak, jak w przypadku TM, że LBA nie może rozwiązać problemu zatrzymania LBA. Ale TM może to rozwiązać dla LBA.

Wreszcie, możesz sobie wyobrazić mocniejsze modele obliczeniowe, wprowadzając Oracle, czyli urządzenia, które mogą udzielać odpowiedzi na określone problemy i mogą być wywoływane przez TM w celu uzyskania odpowiedzi, ale niestety nie istnieją fizycznie. Taka wyrocznia z rozszerzeniem Oracle jest przykładem maszyny T +, którą rozważałem powyżej. Niektóre z nich mogą rozwiązać problem zatrzymania TM (abstrakcyjnie, nie na serio), ale nie mogą rozwiązać własnego problemu Zatrzymania, nawet abstrakcyjnie.

Cóż, zawsze możesz rozważyć maszynę Turinga wyposażoną w wyrocznię dla zwykłego problemu zatrzymania maszyny Turinga. Oznacza to, że twoja nowa maszyna ma specjalną taśmę, na której może napisać opis zwykłej maszyny Turinga i jej dane wejściowe i zapytać, czy ta maszyna zatrzymuje się na tym danych wejściowych. W jednym kroku otrzymujesz odpowiedź i możesz jej użyć do wykonania dalszych obliczeń. (Nie ma znaczenia, czy jest to jeden krok, czy nie: wystarczyłoby, gdyby zagwarantowano, że będzie to skończona liczba kroków).

Istnieją jednak dwa problemy z tym podejściem.

1. Maszyny Turinga wyposażone w taką wyrocznię nie mogą zdecydować o własnym problemie zatrzymania: dowód Turinga na nierozstrzygalność zwykłego problemu zatrzymania można łatwo zmodyfikować do tego nowego ustawienia. W rzeczywistości istnieje nieskończona hierarchia, znana jako „stopnie Turinga”, generowana przez nadanie wyższemu poziomowi hierarchii wyroczni dla problemu zatrzymania poprzedniego.

2. Nikt nigdy nie sugerował żadnego sposobu, w jaki taka wyrocznia mogłaby być fizycznie wdrożona. To wszystko bardzo dobrze jako urządzenie teoretyczne, ale nikt nie ma pojęcia, jak je zbudować.

Zauważ też, że ZFC jest w pewnym sensie słabsza niż naiwna teoria mnogości, a nie silniejsza. ZFC nie potrafi wyrazić paradoksu Russella, podczas gdy naiwna teoria mnogości potrafi. W związku z tym lepszą analogią byłoby pytanie, czy problem zatrzymania jest rozstrzygalny w przypadku słabszych modeli obliczeniowych niż maszyn Turinga. Na przykład problem zatrzymania deterministycznych automatów skończonych (DFA) jest rozstrzygalny, ponieważ gwarantuje się, że DFA zatrzymają się przy każdym wejściu.

Ostrzeżenie: odpowiedź filozoficzna / nie rygorystyczna

To może stać się trochę „filozoficzne”, ale myślę, że pasuje do ducha twojego pytania.

Niepowtarzalna maszyna

Kamieniem węgielnym dowodu problemu zatrzymania jest to, że maszyna Turinga zachowuje się jak funkcja: dla tego samego wejścia zawsze daje taką samą wydajność. Jeśli usuniesz tę właściwość, nie będziesz musiał radzić sobie z „ogólnym” problemem zatrzymania, w tym sensie, że maszyna może odkryć własne właściwości. Ale tracisz również wiele pożądanych teoretycznych właściwości takiej maszyny.

Usuwanie właściwości

To trochę jak przejście od teorii mnogości do teorii kategorii: tracisz niektóre „paradoksony”, tracąc ograniczenia. Ale wynik jest znacznie trudniejszy do opanowania.

W tym przypadku oznacza to: Nie miałbyś pojęcia, czy maszyna przedstawia ci „poprawny” wynik. Gdy tylko zawsze będziesz mógł zdecydować, który wynik jest poprawny, musisz poradzić sobie z jakimś „problemem zatrzymania” poprzez przyłożenie maszyny do siebie i zbudowanie sprzeczności. Taka maszyna prawdopodobnie nie byłaby bardzo przydatna.

Problem zatrzymania nie został sformułowany w celu wyrażenia ograniczeń maszyn Turinga, ale raczej w celu wyrażenia ograniczenia wszystkich układów logicznych, które można wyrazić za pomocą skończonej liczby symboli. Gdy system logiczny będzie w stanie wyrazić rozwiązania problemów o określonej złożoności, będzie miał także możliwość wyrażenia problemów, których nie może rozwiązać. Każde rozszerzenie systemu logicznego wystarczające do wyrażenia rozwiązania wszystkich problemów, których wcześniej nie było w stanie rozwiązać, będzie obejmować także możliwość wyrażenia nowych problemów, których nie może rozwiązać.

Biorąc pod uwagę jakąkolwiek konkretną specyfikację „Ulepszonej maszyny Turinga”, możliwe byłoby określenie „Super-Ulepszonej maszyny Turinga”, która mogłaby zbadać program dla ETM i zgłosić, czy się zatrzyma, ale SETM byłby w stanie analizować programy tylko pod kątem ETM - nie byłby w stanie analizować programów SETM. Nie ma sposobu, aby zdefiniować maszynę, która może analizować programy dla siebie i ustalić, czy się zatrzymają, ponieważ dodanie nowych funkcji stworzyłoby nowe wymagania dla analizatora i nie ma możliwości, aby funkcje „dogoniły” wymagania .

Takie maszyny zostały przewidziane i są nazywane maszynami super-Turinga . Istnieje kilka głównych klas maszyn super-turingowych

• Maszyny liczb rzeczywistych (tj. Komputery analogowe)
• Maszyny Turinga mają nieskończony czas
• Niedeterministyczna maszyna Turinga

Nie wszystkie maszyny super-turingowe mogą rozwiązać problem zatrzymania (w szczególności niedeterministyczne maszyny Turinga). Jednak powstały maszyny koncepcyjne, przynajmniej w eksperymentach myślowych.