Mozna budu trochu (hodne) placat - je to davno, kdy jsem o tom neco mlhave slysel, ale pry teoreticti informatici vymysleli tridu problemu, ktere jsou neco jako "super neresitelne" (nebo jak se to jmenovalo). Jsou to takove problemy, ktere by nebyly resitelne, ani kdyby existovala reseni "obycejnych" neresitelnych problemu (napr. zminovany halting problem).
Dobre ze? (Vice viz kniha: tusim "Algorithmics - The Spirit Of Computing")
V podstate ano - existuji problemy, ktere jsou neresitelne, i kdybychom meli orakulum, ktere by resilo halting problem. Jednoduse receno by se proste halting problem posunul o tridu vys - jedna se o tzv. relativizovany halting problem.
Kazdy program lze napsat jako primitivne rekurzivni predikat (pro laiky: jako primitivni formuli, nebo chcte-li program, ktery obsahuje nejvys elementarni funkce a omezene for-cykly, ale nikoliv while cykly), pred ktery se pripoji prislusny retezec kvantifikatoru (zde je vyznamne patrna souvislost s logikou). Podle slozitosti tohoto kvantifikatoroveho prefixu se zarazuje problem/program do patricne tridy aritmeticke hierarchie. Ta je shora neomezena a na kazdem jejim stupni je mozne najit problem, ktery je resitelny pouze s pouzitim silnejsiho vypocetniho prostredku (tj. vyssiho stupne hierarchie).
Doufam, ze to jako hrube vysvetleni staci.
Pokud bych si do jazyka přidal instrukci pro řešení halting problemu (nebo libovolného jiného v klasických jazycích neřešitelného problému), mohu udělat úplně stejnou konstrukci a halting problem pro tento nový jazyk bude zase v tom samém jazyce neřešitelný :-)
Jo jo, však také důkaz neřešitelnosti halting problemu a důkaz Gödelovy věty o neúplnosti jsou, odhlédneme-li od technických detailů (které u neúplnosti jsou docela nechutné), vlastně totéž.
Dá se ukázat, že pokud by byl Pán Bůh vševědoucí, tak neplatí matematická logika :-) Vyšlo to relativně nedávno v informagice. Důkaz se provádí sporem.
