Dowód, że istnieje co najmniej jeden trywialny program komputerowy, który nie może istnieć

Najpiękniejsze dowody matematyczne, vol. 2, Maxime Coutte.

Artykuł z zeszłego tygodnia dotyczył „Czy niektóre nieskończoności są większe niż inne?” oraz argument Cantor Diagonal. W tym tygodniu chcę podzielić się jednym z moich ulubionych problemów z informatyką teoretyczną.

„Części z czterech wczesnych komputerów, 1962. Od lewej do prawej: płyta ENIAC, płyta EDVAC, płyta ORDVAC i płyta BRLESC-I, pokazujące tendencję do miniaturyzacji.”

Pamiętam, jak w gimnazjum, kiedy zaczynałem informatykę, pomyślałem, że teoretycznie mogę rozwiązać każdy problem obliczeniowy za pomocą odpowiednich narzędzi matematycznych i programowania. Myliłem się. Istnieją teoretyczne ograniczenia dla dowolnej maszyny obliczeniowej i tutaj zobaczymy dowód, że istnieje co najmniej jeden problem logiczny, którego żaden program komputerowy nigdy nie będzie w stanie rozwiązać.

Definiowanie H, niemożliwego programu komputerowego

Program komputerowy P (i) definiujemy jako listę instrukcji P, które po uruchomieniu z wejściem i dają wyjście o.

Na przykład,

to program, który sumuje dwie liczby, które podajesz jako dane wejściowe, oraz

to program, który wykorzystuje inny program - P_add - jako dane wejściowe i przekazuje temu programowi dwa pozostałe dane wejściowe. Robi to, co robi P_add (a, b) i podwaja to.

Kiedy program jest wykonywany, może utknąć, działać wiecznie i nigdy niczego nie wypisywać, na przykład program P_sum, który przechodzi do sumy wszystkich liczb naturalnych, będzie dodawał liczby naturalne na zawsze, nigdy nie kończąc działania (tj. Zatrzymania) i wyprowadzanie wyniku.

Załóżmy teraz, że istnieje program H (P, i), który przyjmuje jako dane wejściowe listę instrukcji P programu P (i) oraz i dane wejściowe P (i) i wyprowadza wartość 1, jeśli P (i) zatrzymać się w pewnym momencie i 0, jeśli P (i) utknie i będzie biegał wiecznie. Mówiąc prosto:

Dlaczego lista instrukcji logicznych H nie istnieje?

Na podstawie dowodu Alana Turinga w artykule „O liczbach obliczalnych, z wnioskiem do Entscheidungsproblem” -1937, udowodnimy, że H. nie może istnieć.

Opierając się na założeniu, że H istnieje, konstruujemy program X (P), który będzie działał wiecznie wtedy i tylko wtedy, gdy H (P, P) = 1 i zatrzyma się wtedy i tylko wtedy, gdy H (P, P) = 0. Innymi słowy,

Możemy teraz rozważyć podanie X (i) własnej listy instrukcji X jako danych wejściowych: X (X).

Dlatego X (X) działa wiecznie wtedy i tylko wtedy, gdy H (X, X) = 1 i X (X) zatrzyma się wtedy i tylko wtedy, gdy H (X, X) = 0. Innymi słowy,

Mamy sprzeczność! Reductio ad absurdum wykazaliśmy, że H nie może istnieć, ponieważ jego istnienie prowadzi do absurdalnych wniosków.

Dlatego program komputerowy, który może ustalić, czy jakikolwiek program komputerowy przy jakimkolwiek wejściu zostanie zablokowany i będzie działał wiecznie lub zakończy działanie, jest niemożliwy. Istnieje co najmniej jeden program komputerowy rozwiązujący problem logiczny, który nie może istnieć.

Referencje, Alan Turing. „O liczbach obliczalnych z aplikacją do Entscheidungsproblem”. 1937.

Nazywam się Max Coutte, współzałożyciel Relativty.com, zestawu VR zaprojektowanego od podstaw, którego kod źródłowy i sprzęt zostały przeze mnie otwarte. Obserwuj mnie na Twitterze @maxcoutte.