[ponton]

Programy, których nie da się napisać

Pewnego dnia Twój kolega wysyła Ci na PW link do programu pasta.exe, który podobno po uruchomieniu wyświetla pastę o serwerowni i kończy swoje działanie. Chciałbyś go uruchomić, ale wiesz, że Twój kolega jest śmieszkiem poza kontrolą i mógłby Ci wysłać zarzutkę, np. program odgrywający Never Gonna Give You Up. Przydałoby się mieć jakieś narzędzie, którym mógłbyś przeskanować program pasta.exe, żeby się upewnić, że wyświetli on pastę i tyle -- nic więcej. Niestety, takiego programu nie ma. Nie dlatego, że nikt go nie napisał, ale dlatego, że nie da się go napisać.

Aby to pokazać, przyjmijmy, że mamy na dysku taki program moderacja.exe, któremu przekazuje się dowolny program i jeśli ten program wyświetla pastę o serwerowni, to pokazuje się komunikat "BAN", a w przeciwnym wypadku jest "OK". Skoro go mamy na dysku, to możemy go użyć w innych programach, które sami napiszemy. Napiszmy zatem taki program troll.exe, który wczyta kod innego programu, uruchomi na nim program moderacja.exe i jeśli otrzyma komunikat "BAN" od moderacji, to od razu się zakończy, a jeśli otrzyma komunikat "OK", to wyświetli pastę o serwerowni. Innymi słowy, jest to program, który wczytuje inny program i zachowuje się przeciwnie niż on -- jeśli on wyświetla pastę, to troll.exe jej nie wyświetla, a jeśli wyświetla, to troll.exe tego nie robi.

Pomyślmy teraz, co by się stało, gdybyśmy uruchomili troll.exe i przekazali mu program... troll.exe. Pamiętajmy, że on działa na opak, czyli wyświetla pastę tylko, jeśli wczytany program tego nie robi. Ale wczytanym programem jest on sam! Jak zatem miałby działać? Jeśli wyświetla pastę, to moderacja pokazuje "BAN", zatem jednak nie wyświetla. Paradoks. To dowodzi, że program moderacja.exe nie może istnieć, bo gdyby istniał, to moglibyśmy napisać paradoksalny program. To trochę jak pójście do wróżki, dowiedzenie się o swojej przyszłości (np. "jutro umrzesz") i oszukaniu przeznaczenia (zabicie się tego samego dnia). ( ͡° ͜ʖ ͡°)

Takie programy, które nie istnieją (jak moderacja.exe) nazywa się w informatyce "problemami nierozstrzygalnymi". Pierwszym odkrytym problemem nierozstrzygalnym jest "problem stopu", udowodnionym przez Alana Turinga w 1936. To prawie 10 lat przed stworzeniem pierwszego komputera! Turing wymyślił matematyczny model reprezentacji obliczeń (maszyna Turinga) i pokazał, że ten model nie jest w stanie rozwiązać problemu stopu. Ponieważ wszystkie współczesne komputery są uproszczoną (bo ma skończoną pamięć) wersją maszyny Turinga, jej ograniczenia także ich dotyczą.

O Turingu lub o maszynie Turinga można jeszcze dużo napisać, np. czym się różni deterministyczna wersja od niedeterministycznej, czyli czym jest słynne P i NP, ale byłoby to za dużo naraz. Mam nadzieję, że kogoś spoza IT to zaciekawiło, bo programiści w większości o tym wiedzą. Na deser XKCD na temat.

#ciekawostki #programowanie #informatyka #ciekawostkiinformatyczne #gruparatowaniapoziomu

[pumpkinguy]

@ponton: O takie wpisy nic nie robiłem, łap zasłużonego plusa ( ͡° ͜ʖ ͡°)

[superbybak]

@ponton: fajnie, ale trochę nieprecyzyjnie.

[sylwester-stallone]

@ponton: masz gdzieś po polsku ten problem stopu?
#dobrycontent ;)

[ponton]

@superbybak co jest nieprecyzyjne?

@sylwester-stallone wkipedia

[superbybak]

@ponton: moim zdaniem nieprecyzyjna jest definicja "pożądanego" działania moderacja.exe i obsługi argumentów w programach. Ogólnie fajna bardzo analogia, ale pomyślałem o kilku pytaniach, które się nasuwają po lekturze wpisu:
- "co zwraca moderacja.exe kiedy pasta.exe się zapętli"?
- "hej, napisałem program parzystapasta.exe który bierze jako argument liczbę i wypisuje pastę tylko jeśli liczba jest parzysta, co zwraca moderacja.exe dla tego programu?"
- "jaki program analizuje troll.exe, który jest podany

[Dralax]

@ponton: To nie jest XKCD

[ponton]

@Dralax: faktycznie xD