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).

 Pastabos 
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 

Kategorija:Algoritmai