Raiso teorema
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
- 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ą.
[taisyti] 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.