Něco jsem napsal a měl bych si to obhájit.
Respekt!
Konkrétně použitelnost znalosti o "nerozhodnutelnosti problému zastavení" pro informatickou praxi. Jednak samotná myšlenka, že výpočetní systémy jsou už ze své "matematické" podstaty něčím inherentně omezeny a existují tam věci, které zcela principiálně nejdou, byla pro mě velice trefnou pointou ihned v době, kdy jsem na ni narazil
Jasně. Velice zajímavé to je, o tom žádná. Ale je to spíš ze soudku "filosofie"
- čili v praxi můžete dostat i zadání, které nejde provést (vymyslel si to nějaký laik, který neví, že to nejde).
Tak k tomu nepotřebuješ HP. Stačí třeba problém kvadratury kruhu
Na přímý příklad z vlastní praxe si nevzpomínám
Kvituju, že to takhle chlapsky přiznáváš, to jsem tady ještě nezažil. Respekt podruhé!
, ale před pár lety jsem četl na jednom fóru od programátora, který si stěžoval, že jeho šéf (manažer-laik, který nezná informatickou teorii) má nápady na zadání, které jsou právě ekvivalentní problému zastavení. Dobře jsem si to zapamatoval, ale link na ten příspěvek už nemám, je to přece jen pár let.
Tak k tomu bych řekl, že bych se klidně vsadil, že ten člověk se pletl a ve skutečnosti ten problém ekvivalentní nebyl. Což jsme zase znovu u toho, že blbě pochopená teorie je skoro horší než ji neznat vůbec
Zaznělo tady to, že člověk nebude nikdy počítat s neomezeným Turingovým strojem - daný problém je tedy řešitelný, když do procesů, jejichž zastavení budete kontrolovat, vložíte nějaká dodatečná omezení. To už tím pádem ale operujete se znalostí této teorie (víte, že omezení jsou potřeba a v jakém směru).
Problém je v tom, že ta omezení jsou inherentní našemu světu. Jinak řečeno: s naprostou jistotou vím, že nikdo z nás nikdy neviděl a nikdy neuvidí stroj s potenciálně nekonečným množstvím stavů. Čili si dovolím říct, že nikdy nebude
doopravdy potřebovat řešit, jestli se takový stroj zastaví nebo ne
Nebo ještě jinak: problém zastavení TM je do velké míry problém typu "jak by fungovala demokracie, kdyby byl prezident celý ze zlata". Takový trochu zvláštní problém
A když odstraním ten předpoklad "prezident ze zlata", tak se z toho nestane nějaký divnější problém. Divnější je tam ten předpoklad přidat, než ho odebrat
No, takže všichni z nás se ve škole o zastavení TM učili a máme nějaký mlhavý pocit, že by se to někdy mohlo někomu hodit. Možná. Tak nějak... A co víme o daleko praktičtějším problému zastavení LBA? Typicky nic. A vůbec nás to netrápí. Zabývali jsme se tím, jak by fungoval stát s prezidentem ze zlata, ale jak by fungoval stát s prezidentem z masa a kostí, to už jsme nějak nestihli. Docela sranda, ne?
107 Odpovědí
27902 Zhlédnutí