Raiso teorema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
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[taisyti | redaguoti kodą]

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.