Raiso teorema

Šiam straipsniui ar jo daliai trūksta išnašų į šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

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

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.