Czy problem zatrzymania można „rozwiązać”, przechodząc do opisu obliczeń wyższego poziomu?

21

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?

H2CO3
źródło
1
Witamy w Computer Science Stack Exchange. Przeczytaj cs.stackexchange.com/tour.if , jeśli jeszcze tego nie zrobiłeś. --- Czego próbowałeś, aby uzyskać mocniejszy model niż TM? Co cię blokuje?
babou
2
@babou Przeciwnie, potrzebujesz mniej wydajnego modelu.
Yuval Filmus
2
@YuvalFilmus Cóż, OP żąda mocniejszego, a nie słabszego modelu. --- z przeprosinami za H2CO3 ... Moje pytanie było w rzeczywistości żartem, ponieważ jest to standardowe pytanie, gdy ludzie przesyłają pracę domową jako pytanie. Oczywiście nie było to właściwe, ponieważ nikt nie spodziewa się, że znajdziesz taki model. Mam nadzieję, że nie weźmiesz tego zbyt kwaśno.
babou
1
Możesz przeczytać o Hypercomputation en.wikipedia.org/wiki/Hypercomputation .
Eric Towers

Odpowiedzi:

15

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.

Babou
źródło
Zakładając, że ZFC jest spójny, nadal jest niekompletny, tzn. Istnieją zdania, których nie możemy ani udowodnić, ani obalić przez ZFC, i jest to ściśle związane z nierozwiązywalnym problemem zatrzymania, gdyby zatrzymanie było możliwe do rozwiązania, moglibyśmy udowodnić lub obalić wszystkie zdania. To jest matematyka i nie jest to niekonsekwencja do rozwiązania, ale także twierdzenie (Gödel)
Hernan_eche
@Hernan_eche Cóż ... tak i ... co ...? Jeśli uważasz, że niekonsekwencja nie jest gorsza niż niekompletność, to twój osobisty osąd. Wątpię, czy większość matematyków by się zgodziła. Możesz nie lubić TM, które się nie kończą. Ale czy chciałbyś, aby lepiej zawsze kończyły, mówiąc czasem „tak”, a czasem „nie” przy tym samym wejściu. Co byś zrobił z odpowiedzią? A jeśli uważasz, że niedeterminizm ... pomyśl dwa razy.
babou
Skomentowałem tylko, aby wyjaśnić, że Informatyka i Matematyka walczą z tymi samymi problemami, aby uniknąć czytelników, którzy źle interpretują odpowiedź, tak jakby matematyka została rozwiązana problemy podstawowe z ZFC, a problem zatrzymania był tylko problemem informatycznym, tak nie jest, istnieje jeden do jednego związek między niekompletnością a problemem zatrzymania, to ten sam problem. Nie uważam, że niekompletność jest gorsza lub lepsza niż niekonsekwencja, ale myślę, że niekompletność stanie się niekonsekwencją, jeśli będziesz chciał budować systemy wyższego rzędu.
Hernan_eche
17

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.

David Richerby
źródło
Wydaje mi się, że każdy problem automatów rozwiązuje jego własny problem zatrzymania, jeśli jest to trywialne, tzn. Albo wszystkie się zatrzymują, albo żadna z nich nie działa (co w tym przypadku można uznać za dziwne).
babou
1
@babou: co z automatami, w których maszyna 0 zapętla się na zawsze, maszyna 1 wyprowadza FALSE, jeśli jej wejście to 0, w innym przypadku PRAWDA, a następnie zatrzymuje się. Wszystkie pozostałe maszyny wysyłają FAŁSZ, a następnie zatrzymują się. Czy to rodzina automatów, w których program 1 rozwiązuje niebanalny problem zatrzymania? A może nie jest to nawet rodzina automatów z powodu braku jakiejś własności, np. Jakiejkolwiek kompozycji?
Steve Jessop
@ SteveJessop Cóż, ty (i Davis Richerby) prawdopodobnie macie rację. Niepokoi mnie to, że jest to wymyślony przykład. Budujesz bardzo słabą rodzinę, tak że jedna maszyna w rodzinie jest decydującym czynnikiem dla całej rodziny. Ale, jak podejrzewasz siebie (patrz uwaga na temat kompozycji), może brakować podstawowych właściwości zamknięcia, aby problem mógł zostać trywializowany. Nie mam gotowej odpowiedzi i zgadzam się, że moja uwaga wymaga większej kwalifikacji co do tego, co stanowi rodzinę automatów, ale twój kontrprzykład nie pozostawia mnie przekonanym.
babou
3

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.

stefan.schwetschke
źródło
1
Dziękuję, że ta „niepowtarzalna maszyna” brzmi właściwie całkiem interesująco. Nie czuję się wystarczająco kompetentny, aby wygodnie powiedzieć trochę mądrości na temat sprytnych programów do samokontroli (ponieważ instynkt mam taki, że nadal można je wyrazić jako maszyny Turinga), ale uważam, że mogą one być bardzo przydatne w przypadku niektórych problemów.
H2CO3,
1
Jak podałby przykład braku powtarzalności? Jak byś zdefiniował zatrzymanie w takim przypadku. Główną trudnością jest to, że kiedy próbujesz zdefiniować dziwny model obliczeniowy, zwykle gedanken, musisz zdefiniować znaczenie zatrzymania i jakiego rodzaju dane wejściowe ma analizować maszyna decydująca, a być może kilka innych nietrywialnych rzeczy. Zobacz na przykład przypadek niedeterminizmu . Nie wspominając już o kwestii tego, co można uznać za model obliczeniowy (prawdopodobnie nie jest to zbiór maszyn ad hoc).
babou
1
@ H2CO3 Niepowtarzalna maszyna jest jedynie rodzajem „eksperymentu Gedankena” na tym, jaką własność musisz poświęcić, aby wyjść z „ogólnego problemu zatrzymania” (budowanie sprzeczności, pozwalając maszynie na sprawdzenie się). Dostaniesz maszynę, która czasem jest odpowiednia, ale nie wiesz, kiedy. To jest jak program, który oblicza numery loterii na następny tydzień. Mogę z łatwością zapewnić ci taki program. Trudno ci zdecydować, który z wielu programów, które ci dam, jest poprawny ...
stefan.schwetschke
2

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 .

supercat
źródło
1

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.

Cort Ammon - Przywróć Monikę
źródło