Raiso teorema
- Raiso teorema
- bet kuri netriviali apskaičiuojamų funkcijų savybė yra algoritmiškai neišsprendžiama.
Turima galvoje, kad nėra vieno algoritmo, kuris, turėdamas funkcijos ar algoritmo aprašą, nustatytų to algoritmos netrivialią savybę, t. y. tokią savybę, kurią vienos funkcijos ar algoritmai turi, o kiti – ne. Tokių savybių pavyzdžiai gali būti funkcijos periodiškumas, lyginumas ar nelyginumas. Kitas pavyzdys toks: turint dviejų algoritmų aprašus bendru atveju neįmanoma nustatyti, ar jie apskaičiuoja tą pačią funkciją.
Raiso teoremą 1953 m. paskelbė amerikietis matematikas ir logikas Henris Gordonas Raisas (Henry Gordon Rice).[1]
Pastabos redaguoti
Jei neegzistuoja algoritmas, išsprendžiantis problemą bendru atveju, tai visiškai nereiškia, kad neegzistuoja algoritmas, išsprendžiantis tą pačią problemą daliniu atveju.
Šaltiniai redaguoti
- ↑ Rice, H. G. (1953). „Classes of Recursively Enumerable Sets and Their Decision Problems“. Transactions of the American Mathematical Society. 74 (2): 358. doi:10.2307/1990888.