Dlaczego tak naprawdę problem zatrzymania jest tak ważny?

Nie rozumiem, dlaczego problem zatrzymania jest tak często wykorzystywany do odrzucenia możliwości ustalenia, czy program się zatrzymuje. Wikipedia [artykuł] [1] poprawnie wyjaśnia, że ​​deterministyczna maszyna ze skończoną pamięcią zatrzyma lub powtórzy poprzedni stan. Możesz użyć algorytmu, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności przestrzennej O (1).

Wydaje mi się, że dowód na problem zatrzymania jest niczym więcej niż tak zwanym „paradoksem”, wewnętrznie sprzeczną (przynajmniej cykliczną) sprzecznością w taki sam sposób, jak paradoks Kłamcy. Jedyny wniosek, jaki wyciąga, jest taki, że funkcja zatrzymania jest podatna na tak źle sformułowane pytania.

Tak więc, wyłączając programy paradoksalne, funkcja zatrzymania jest rozstrzygalna. Dlaczego więc uważamy to za dowód przeciwny?

4 lata później : kiedy to napisałem, właśnie obejrzałem to wideo . Programista otrzymuje niektóre programy, musi ustalić, które z nich kończą się, a film wideo wyjaśnia, dlaczego jest to niemożliwe. Byłem sfrustrowany, ponieważ wiedziałem, że biorąc pod uwagę niektóre arbitralne programy, istnieje możliwość, że protagonista może udowodnić, czy zostały zakończone. Pojęcie ogólności jakoś zaginęło. Jest to różnica między powiedzeniem „niektóre programy nie mogą zostać zakończone” a „nie można udowodnić, że żaden program się kończy”. Wiele algorytmów zostało formalnie wykazanych, aby to zrobić. Nieumiejętność rozróżnienia tego w każdym odnośniku znalezionym w Internecie była sposobem, w jaki doszedłem do tytułu tego pytania. Z tego powodu naprawdę doceniam odpowiedź która redefiniuje funkcję zatrzymania jako potrójną zamiast wartości logicznej.

Ponieważ wiele naprawdę praktycznych problemów to ukrywanie problemu. Rozwiązanie ich rozwiązuje problem zatrzymania.

Chcesz kompilatora, który znajdzie najszybszy możliwy kod maszynowy dla danego programu? Właściwie problem zatrzymania.

Masz JavaScript, z niektórymi zmiennymi na wysokim poziomie bezpieczeństwa, a niektóre na niskim poziomie bezpieczeństwa. Chcesz się upewnić, że osoba atakująca nie może uzyskać informacji o wysokim poziomie bezpieczeństwa. To także tylko problem zatrzymania.

Masz parser dla swojego języka programowania. Zmieniasz go, ale chcesz się upewnić, że nadal analizuje wszystkie programy, których używał. Właściwie problem zatrzymania.

Masz program antywirusowy i chcesz sprawdzić, czy kiedykolwiek wykona złośliwą instrukcję. Właściwie to tylko problem zatrzymania.

Jeśli chodzi o przykład z wikipedii, tak, można modelować nowoczesny komputer jako maszynę o skończonym stanie. Ale są z tym dwa problemy.

1. Każdy komputer byłby innym automatem, w zależności od dokładnej liczby bitów pamięci RAM. Nie jest to więc przydatne do badania określonego fragmentu kodu, ponieważ automat zależy od komputera, na którym może działać.

2. Potrzebujesz stanów, jeśli masz n bitów RAM. Tak więc dla twojego nowoczesnego komputera o pojemności 8 GB, to 2 32000000000 . Jest to tak duża liczba, że ​​wolfram alfa nawet nie wie, jak ją interpretować. Kiedy robię 2 10 9 , mówi, że ma 300000000 cyfr dziesiętnych. Jest to zdecydowanie za dużo do przechowywania na normalnym komputerze.$2^n$$2^{32000000000}$$2^{10^9}$$300000000$

Problem zatrzymania pozwala nam rozumować względną trudność algorytmów. Daje nam to do zrozumienia, że ​​istnieją pewne algorytmy, które nie istnieją, że czasami wszystko, co możemy zrobić, to zgadnąć problem i nigdy nie wiedzieć, czy go rozwiązaliśmy.

Gdybyśmy nie mieli problemu z zatrzymaniem, nadal szukalibyśmy magicznego algorytmu Hilberta, który wprowadzałby twierdzenia i wyprowadzałby, czy są prawdziwe, czy nie. Teraz wiemy, że możemy przestać szukać i możemy dołożyć starań, aby znaleźć heurystykę i najlepsze metody rozwiązywania tych problemów.

AKTUALIZACJA: Aby rozwiązać kilka problemów poruszonych w komentarzach.

@Tyler Fleming Cloutier: „Bezsensowny” problem pojawia się w dowodzie, że problem zatrzymania jest nierozstrzygalny, ale sednem nierozstrzygalności jest naprawdę nieskończona przestrzeń poszukiwań. Szukasz obiektu o danej właściwości, a jeśli nie istnieje, nie ma sposobu, aby wiedzieć, kiedy skończysz.

Trudność problemu może być związana z liczbą posiadanych kwantyfikatorów. Próbując pokazać, że istnieje ( ) obiekt o dowolnej właściwości, musisz szukać, aż go znajdziesz. Jeśli nie istnieje, nie ma możliwości (ogólnie), aby to wiedzieć. Udowodnienie, że wszystkie obiekty ( ∀ ) mają właściwość, jest trudne, ale można wyszukać obiekt bez właściwości, aby go obalić. Im więcej jest alternatywnych opcji dla forall i istnieje, tym trudniejszy jest problem.$\exists$$\forall$

Aby uzyskać więcej informacji na ten temat, zobacz Hierarchia arytmetyczna . Wszystko powyżej jest nierozstrzygalne, chociaż poziom 1 jest częściowo rozstrzygalny.$\Sigma^0_0=\Pi^0_0$

Można również wykazać, że istnieją nierozwiązywalne problemy bez użycia nonsensownego paradoksu, takiego jak problem Haltinga lub paradoksu Liarsa. Maszynę Turinga można zakodować za pomocą ciągu bitów, tj. Liczby całkowitej. Ale problem można zakodować jako język, tj. Podzbiór liczb całkowitych. Wiadomo, że nie występuje bijectja między zbiorem liczb całkowitych a zbiorem wszystkich podzbiorów liczb całkowitych. Więc muszą być pewne problemy (języki), które nie mają powiązanej maszyny Turinga (algorytmu).

@Brent: tak, to przyznaje, że jest to rozstrzygalne w przypadku nowoczesnych komputerów. Ale decyduje o tym konkretna maszyna. Jeśli dodasz dysk USB z miejscem na dysku lub możliwością przechowywania w sieci lub czymkolwiek innym, oznacza to, że urządzenie się zmieniło, a wynik nadal się nie utrzymuje.

Trzeba też powiedzieć, że wiele razy algorytm mówi „ten kod się zatrzyma”, ponieważ kod zawiedzie i zabraknie pamięci, a dodanie jednego dodatkowego fragmentu pamięci spowoduje, że kod odnieść sukces i dać inny wynik.

Chodzi o to, że maszyny Turinga nie mają nieskończonej ilości pamięci. Nigdy nie ma czasu, aby na taśmie zapisywano nieskończoną liczbę symboli. Zamiast tego maszyna Turinga ma „niezwiązaną” pamięć, co oznacza, że ​​możesz nadal otrzymywać więcej źródeł pamięci, gdy jej potrzebujesz. Komputery są takie. Możesz dodać pamięć RAM lub USB, dyski twarde lub pamięć sieciową. Tak, kończy Ci się pamięć, kiedy zabraknie atomów we wszechświecie. Ale posiadanie nieograniczonej pamięci jest o wiele bardziej użytecznym modelem.

W praktyce jest to ważne, ponieważ pozwala powiedzieć nieświadomym szefom, że „to, o co prosisz, jest matematycznie niemożliwe”.

Problem zatrzymania i różne problemy z kompletną NP (np. Problem sprzedawcy podróżującego) pojawiają się często w postaci „Dlaczego nie możesz po prostu stworzyć programu, który robi X?” I musisz być w stanie wyjaśnić dlaczego jest to niemożliwe lub niemożliwe do wykonania w pozostałym okresie życia wszechświata.

Należy pamiętać, że możliwe jest zaprojektowanie języka, który nie jest kompletny dla Turinga, więc można go analizować, zabraniając nieograniczonej rekurencji i iteracji.

Możesz użyć algorytmu, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności przestrzennej O (1).

Aby to zrobić, musisz przechowywać co najmniej dwie kopie stanu częściowego programu w pamięci plus koszty programu sprawdzającego. Tak więc na danym komputerze nie można przetestować wszystkich programów, które mogą być uruchomione na tym komputerze, tylko programy, które działają na mniejszym komputerze z mniej niż połową ilości pamięci.

Problemu zatrzymania dla danego komputera o skończonych rozmiarach nie można rozwiązać na tym komputerze o skończonych rozmiarach. Można to rozwiązać tylko na większym komputerze. (Dotyczy to każdej metody, nie tylko tej, którą zaproponujesz. Nie przedstawię formalnego dowodu, ale oto sedno. Jeśli komputer C może uruchamiać N różnych programów, z których co najmniej jedno P nie kończy się , to komputer V, który może sprawdzić, czy te N programów zatrzymuje się, musi być zdolny do uruchamiania również N. różnych programów weryfikujących. Jeśli C i V są tym samym komputerem, P nie jest jednym z N różnych programów uruchamianych przez V, więc komputer musi uruchamiać co najmniej N + 1 różnych programów, co jest sprzeczne z założeniem, że C uruchamia N różnych programów).

$M$$2^M$$2^{56}$

Liczby tam pokazują, że myślenie o komputerze jako maszynie skończonej jest rzadko praktyczne. Liczba stanów może być skończona, ale jest zadziwiająco, niepraktycznie ogromna. Jedynym sposobem na rozumowanie programów innych niż zabawki jest streszczenie, nie poprzez wyliczanie stanów, ale poprzez logiczne rozumowanie.

Tak więc z wyłączeniem programów paradoksalnych problem zatrzymania jest rozstrzygalny

Paradoks nie wynika z problemu, ale z próby rozwiązania. Dla każdego programu istnieje algorytm, który mówi „tak”, jeśli program się zakończy, i „nie”, jeśli program się nie zakończy. To banalne: albo print "yes"albo print "no"zrobi. Problem polega na ustaleniu, do którego należy zadzwonić. Niemożność rozwiązania problemu zatrzymania oznacza, że ​​nie ma algorytmu, aby dokonać tego ustalenia. Powodem, dla którego dowód używa argumentu diagonalizacji, jest to, że musi on wykazać, że nierozwiązanie działa; aby to zrobić, zaczyna się od arbitralnie rzekomego rozwiązania i pokazuje, że musi pominąć niektóre programy, konstruując pominięty program. Diagonalizacja (to, co niewłaściwie nazywasz „paradoksem”), leży w konstrukcji, a nie w wynikowym programie. Powstałe programy nie są autoreferencyjne.

Istnieje bardziej ogólny wynik zwany twierdzeniem Rice'a, które stwierdza, że każda nietrywialna właściwośćprogramów jest nierozstrzygalna - każda właściwość, która zależy tylko od zachowania programu, a nie w określony sposób (np. „czy kod źródłowy składa się z mniej niż 42 znaków?” jest wyraźnie rozstrzygalna, podczas gdy „czy istnieje program, którego kod źródłowy składa się z mniej niż 42 znaków i który zwraca ten sam wynik dla wszystkich danych wejściowych? ”nie jest, ani„ czy ten program nigdy nic nie wyświetla? ”). Zatrzymanie to tylko jeden przykład. Jest to ważne, ponieważ często pojawia się w praktyce (zwykle chcemy wiedzieć, czy program zwróci wynik w rozsądnym czasie, biorąc pod uwagę skończone zasoby komputera, na którym działa, ale ponieważ rzadko jest to praktycznie możliwe, jesteśmy odpowiedzialni gotów zadowolić się prostszym pytaniem, czy program ostatecznie zakończy działanie, biorąc pod uwagę wystarczającą ilość czasu i pamięci).

Wydaje mi się, że problem zatrzymania jest niczym więcej niż tak zwanym „paradoksem”, wewnętrzną sprzecznością (przynajmniej cykliczną) w taki sam sposób, jak paradoks Kłamcy. Jedyny wniosek, jaki wyciąga, jest taki, że funkcja zatrzymania jest podatna na tak źle sformułowane pytania

Nie, nie o to chodzi w problemie zatrzymania. Paradoksy, takie jak paradoks kłamcy, nie są prawdziwe ani fałszywe, po prostu nie mają sensu. Z drugiej strony algorytm deterministyczny albo zatrzyma się na danym wejściu, albo będzie działał na zawsze. Funkcja halts(program, input)ma doskonale dobrze zdefiniowaną, deterministyczną wartość dla każdego programu, dla każdego wejścia. Po prostu nie możemy zdecydować o tym w żadnym programie. Lub ściślej: nie możemy napisać programu, który może decydować o nim dla każdej pary program / wejście.

$\Sigma(n):=$$n$$n$$n$$n$$\Sigma(n)$

Nie rozumiem, dlaczego problem zatrzymania jest tak często wykorzystywany do odrzucenia możliwości ustalenia, czy program się zatrzymuje. Artykuł w Wikipedii poprawnie wyjaśnia, że ​​deterministyczna maszyna ze skończoną pamięcią zatrzyma lub powtórzy poprzedni stan. Możesz użyć algorytmu, który wykrywa, czy lista połączona zapętla się w celu zaimplementowania funkcji zatrzymania o złożoności przestrzennej O (1).

Po pierwsze tak, teoretycznie sensowne jest postrzeganie prawdziwego komputera, który ma skończoną pamięć, jako skończonej maszyny stanów. Ale w praktyce liczba stanów prawdziwego komputera jest tak duża, że ​​rzeczywiste komputery są znacznie lepiej modelowane przez maszyny Turinga lub inne nieskończone modele obliczeniowe stanów.

Po drugie, nawet teoretycznie sensowne jest postrzeganie nowoczesnego komputera jako nieskończonej maszyny stanów. Maszyna Turinga nie ma nieskończonej taśmy, ma taśmę, którą można zawsze przedłużyć, gdy w maszynie zabraknie pamięci. I czy nie jest to dokładnie to, co możemy zrobić z prawdziwymi komputerami? (A jeśli skończy się przestrzeń adresowa procesora, możemy użyć chmury itp.)

Wydaje mi się, że problem zatrzymania jest niczym więcej niż tak zwanym „paradoksem”, wewnętrzną sprzecznością (przynajmniej cykliczną) w taki sam sposób, jak paradoks Kłamcy. Jedyny wniosek, jaki wyciąga, jest taki, że funkcja zatrzymania jest podatna na tak źle sformułowane pytania. Tak więc z wyłączeniem programów paradoksalnych problem zatrzymania jest rozstrzygalny. Dlaczego więc uważamy to za dowód przeciwny?

$H$$P$$x$$H$$P$$x$

Dowód Turinga o nierozstrzygalności problemu zatrzymania wykorzystuje sztuczkę podobną do paradoksu Kłamcy, tak. Paradoks jest często definiowany jako pozorna sprzeczność, a niektórzy ludzie wywnioskowali z tego, że paradoks nie jest zatem prawdziwy sprzecznością. Jednak paradoks Russela (formalny odpowiednik paradoksu paradoksu kłamcy) pokazał prawdziwą sprzeczność w matematyce, a dowód na nierozstrzygalność problemu zatrzymania wykorzystuje prawdziwą sprzeczność dla jego dowodu sprzeczności.

jmite bardzo ładnie odpowiedział na pytanie. Dodaję małą notatkę dotyczącą postrzeganego podobieństwa z „Paradoksem kłamcy”, który, jak sądzę, jest spowodowany przez użycie mechanizmu samoodniesienia.

Odniesienia do siebie nie są paradoksalne!

Odniesienia do siebie są naprawdę użytecznym narzędziem w obliczeniach (że algorytm może odnosić się do swojego kodu, odbicia ) i języka ludzkiego (że możemy odnosić się do siebie, do samoświadomości ).

Problemem, który powoduje paradoks Kłamcy, nie jest samookreślenie, lecz próba użycia predykatu prawdy dla (formalnego) języka wewnątrz języka. Będzie to powodować problemy nawet bez odniesienia do siebie, nie potrzebujemy możliwości używania odniesienia do siebie, aby uzyskać paradoks: odniesienie można wyeliminować! . Sprawiłoby to, że zdanie byłoby mniej miłe i zwięzłe, ale nie jest trudne do wykonania. Zasadniczo tak jest udowodniono twierdzenie Kleene'a o punkcie stałym . Paradoks Kłamcy sugeruje, że prawda wypowiedzi w (formalnym) języku jest transcendentalna w stosunku do tego języka, a nie to, że samookreślenie jest problematyczne.

Wydaje mi się, że twój dyskomfort nie wynika z nierozstrzygalności problemu zatrzymania (dla maszyn Turinga), ale z akceptacją maszyn Turinga jako modelu teoretycznego dla komputerów. Zazwyczaj (choć nie zawsze) maszyny Turinga (i podobne modele obliczeniowe, takie jak maszyny o dostępie swobodnym ) są bardzo przydatne do dyskusji na temat obliczeń na rzeczywistych komputerach niż automaty skończone i istnieją ku temu dobre powody (należy pamiętać, że maszyna Turinga nie ma nieskończona ilość pamięci, ma nieograniczoną ilość pamięci i są to różne rzeczy: nieograniczona oznacza, że ​​możemy zapewnić maszynie więcej pamięci, gdy potrzebuje, a nie to, że używa nieskończonej ilości pamięci).

Jasne, jeśli chcesz myśleć o komputerach jako automatach skończonych, a to ma sens dla twojego celu, wtedy problem zatrzymania automatów skończonych jest rozstrzygalny (a przez rozstrzygający rozumiemy rozstrzyganie przez maszynę Turinga, a nie przez automaty skończone). Nie to jednak ludzie zwykle mają na myśli, gdy używają problemu zatrzymania, mają na myśli problem zatrzymania dla maszyn Turinga.

$s$$2^s$

problem zatrzymania wprowadził nową matematyczną koncepcję „nierozstrzygalności”, która wcześniej nie istniała w matematyce. był to („pozornie paradoksalny”) dowód, że niektóre problemy nie mają „dowodów”. jest to związane z Godelowską koncepcją niewiarygodności. Twierdzenie Godelsa poprzedzało sformułowanie problemu zatrzymania przez Turinga o kilka lat. Wynik Godels był wówczas uważany za raczej abstrakcyjny i był znany tylko badaczom i specjalistom. Sformułowanie Turingsa wykazało, że zasada nierozstrzygalności była związana z wysoce praktycznymi / pragmatycznymi / stosowanymi pytaniami w informatyce, takimi jak ustalenie, czy zatrzymują się arbitralne programy i jest uważana za znacznie mniej teoretyczną koncepcję, pojawia się w nowoczesnych wyzwaniach, takich jak „ (wyzwanie, czy komputery potrafią odkryć twierdzenia) i udowodnienie zakończenia programu.

Innym interesującym kątem jest to, że istnieją pewne bardzo stare problemy w teorii liczb (diofantycznej) wywodzące się z Greków, które nie są udowodnione przez tysiąclecia. istnieje podobny wynik, że pytania ogólne dotyczące równań diofantycznych są nierozstrzygalne, zwane 10. problemem / twierdzeniem Hilberta . Hilbert żył na przełomie XIX i XX wieku i zaproponował jako program badawczy, że matematyka może znaleźć systematyczne podejście do problemów matematycznych. wyzwanie to / plan został poważnie uderzony odkryciem nierozstrzygalności sprzed kilkudziesięciu lat. nierozstrzygalność jest nadal bardzo zaawansowanym obszarem badań, a granica między nierozstrzygalnymi i rozstrzygalnymi problemami prawdopodobnie zawsze będzie przedmiotem dalszych badań i analiz.

Wydaje się, że mylisz klasyczny dowód oparty na „samoreferencji”, że problemu Halting nie da się rozwiązać za pomocą samego problemu Halting (aka Halt).

Ten program autoreferencyjny - program, który zatrzymuje się tylko wtedy, gdy się nie zatrzymuje - jest skonstruowany w celu ułatwienia udowodnienia, że ​​nie można rozwiązać zadania Halt. Fakt, że udowodniliśmy, że X jest niemożliwy za pomocą techniki Y, nie oznacza, że ​​Y jest jedynym powodem, dla którego nie możemy rozwiązać X.

Innymi słowy, nie tylko nie możemy rozwiązać problemu Halt, ale nie możemy wykryć, że program jest rodzajem programu, którego nie jesteśmy w stanie ustalić, czy się zatrzyma, z wyjątkiem prymitywnej miary, takiej jak „jeśli uruchomienie zajmuje więcej niż 1 minutę, udawaj nie zatrzymuje się ”.

Jeśli zaczniesz od problemu zatrzymania i zredukujesz do niego inne problemy, w końcu osiągniesz punkt, w którym zredukowałeś prawie każde pytanie dotyczące programów na ten temat. Kończymy twierdzeniem Rice'a:

Niech S będzie nietrywialną własnością ^{1, którą} akceptuje Maszyna Turinga. Oznacza to, że istnieje co najmniej jedna maszyna Turinga, która akceptuje dane wejściowe o właściwości S, i taka, która nie.

Wówczas nierozstrzygalne jest, czy dana maszyna Turinga T akceptuje dane wejściowe o właściwości S.

Chcesz wiedzieć, czy maszyna Turinga akceptuje nawet liczby całkowite? Niezdecydowany.

Chcesz wiedzieć, czy maszyna Turinga akceptuje sekwencje arytmetyczne? Niezdecydowany.

Możesz rozumować ogólnie o wnętrznościach Turinga. Możesz uzasadnić konkretną Maszynę Turinga i udowodnić, czy zatrzyma / zaakceptuje sekwencję / etc. Ale nie możesz wiedzieć, czy twoja technika będzie działać na następnej maszynie Turinga, którą ją karmisz.

¹ Przez property ofto nie obejmuje mechanizmu tego, w jaki sposób jest akceptowany - tylko tego, co jest akceptowane. „Akceptuje co 100 lub mniej kroków” to właściwość akceptowana, a nie akceptowana.

Masz rację, że problem zatrzymania, tak jak powszechnie się to przedstawia i stwierdza, jest po prostu gotcha. Nie dowodzi, że nie może istnieć funkcja zatrzymania o trzech wartościach („zatrzymania”, „pętli”, „nie wiem”), która w praktyce zawsze zwraca „zatrzymania” lub „pętle” i zwraca tylko „don” na przykład dla specjalnie skonstruowanych skrzynek narożnych.

Dwa powody, dla których problem zatrzymania jest znaczący:

1) Jest to jeden z pierwszych problemów niemożliwych do rozstrzygnięcia. Nawet gdyby hipotetycznie istniał tylko jeden „nie wiem”, nadal byłby on bardzo interesujący matematycznie.

2) Niektóre problemy ograniczają się do problemu zatrzymania, w którym złośliwy atakujący może dostarczyć sprawę do analizy. Zmusza nas to do zaakceptowania faktu, że mogą istnieć ważne przypadki, które wciąż musimy odrzucić.

Po zastanowieniu się nad drugim punktem, analiza oprogramowania jest trudnym problemem, chociaż poczyniono znaczne postępy zarówno w zakresie analizy, jak i projektowania języka, aby ułatwić analizę. Jeśli możesz wykazać, że pewne zadanie jest podobne do analizy oprogramowania, tak, jest to trudne z dużą literą H. „Jest to niemożliwe, ponieważ oznaczałoby rozwiązanie problemu zatrzymania”, chociaż technicznie błędne lub nieistotne w wielu przypadkach, często jest używane skrót dla tej obserwacji.

Eric Hehner w swojej sprzecznej argumentacji wysuwa szereg artykułów, które dowodzą, że nierozwiązywalność problemu „Stop” jest często źle rozumiana. Artykuły: „Epimenides, Gödel, Turing: wieczna złota plątanina”, „Problemy z problemem stopu”, „Rekonstrukcja problemu stopu” i „Problem stopu” można znaleźć tutaj . Aby ta odpowiedź nie była „tylko linkiem”, postaram się streścić jeden z jego wniosków, ale nie argument.

, więc nie powinniśmy uważać za tak niezwykłe, że nie ma programu do rozwiązania problemu zatrzymania. Standardowy widok jest taki, że istnieje dobrze zdefiniowany predykat h taki, że$f(0)=1 \;\land\; f(0)=2$$h$$h(M)$$M$$H$$h$$h$

Chciałbym przedstawić inne wyjaśnienie znaczenia problemu zatrzymania, który dotyczy ludzi, a nie maszyn.

To ostatni wykład z kursu Struktura i interpretacja MIT 1986 ; profesor pyta: „Czy są jakieś pytania?” i przygotowuje się do zakończenia wykładu, gdy jeden ze studentów zapyta: „Czy to ostatnie pytanie?”

Pomyśl o tym przez chwilę. Jak nauczyciel może na to odpowiedzieć? Jeśli uczeń zdecyduje się zaprzeczyć nauczycielowi, nie ma ważnej odpowiedzi, którą może udzielić nauczyciel - to tak jak problem z zatrzymaniem.

Jesteśmy przyzwyczajeni do abstrakcyjnego myślenia o problemie zatrzymania, przy użyciu funkcji i maszyn, ale jest on o wiele głębszy. Zasadniczo oznacza to, że istnieją doskonale ważne pytania, na które nie można odpowiedzieć.

PS: Jeśli nie wiesz, o którym kursie mówię, obejrzyj to, to niesamowite.

Mogę łatwo napisać program, który ma dane wejściowe n, albo wypisuje najmniejszą liczbę pierwszą p> n, że p + 2 jest również liczbą pierwszą, lub działa wiecznie, jeśli takie p nie istnieje. Jeśli potrafisz rozwiązać problem, aby przewidzieć, czy mój program zatrzymuje się przy każdym wejściu, właśnie rozwiązałeś hipotezę Twin Prime.

Jest całkiem możliwe, że ta hipoteza okaże się nierozstrzygalna, w takim przypadku mielibyśmy prosty program, w którym program zatrzymania zawodzi.