Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele Kuidas lahendamatust näidata (plaan): Näitame, et algoritme on sama palju, kui täisarve (lihtne) Näitame, et probleeme on vähemalt sama palju, kui reaalarve (veidi keerulisem) Näitame, et reaalarve on lõpmatult rohkem kui täisarve (Cantori üks teoreeme) Cantori teoreem ütleb üldisemalt, et mingi hulga H kõigi alamhulkade hulk on suurema võimsusega kui see hulk H. Poollahenduvus Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. Mõne H jaoks on ülesanne lahenduv: näiteks, kui H on paarisarvude hulk, kui H on algarvude hulk jne, Mõne H jaoks ülesanne ei ole lahenduv: näiteks, kui H on arvude hulk, millele vastavad programmid peatuvad. Poollahenduvus tähendab, et kui X juhuslikult kuulub hulka H, siis me saame seda algoritmiga alati näidata. Kui ei kuulu H-i, siis ei saa alati. Strong AI:
programmeerimiskeeles –valime näiteks C •Iga C programm on sisuliselt string •String omakorda on teatud kahendarv, mis teisendatult on kümnendsüsteemi täisarv •Iga täisarv loomulikult ei presenteeri üht algoritmi, küll aga vastupidi •Saab näidata, et probleemide hulk on samas suurusjärgus reaalarvude hulgaga •Cantori teoreem matemaatikas näitab, et reaalarve on rohkem kui täisarve. ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 27 Poollahenduvus •Olgu ülesandeks tuvastada, kas täisarv X kuulub mingisse lõpmatusse täisarvude alamhulka H. .Mõne H jaoks on ülesanne lahenduv: näiteks, kui H on paarisarvude hulk, kui H on algarvude hulk jne, .Mõne H jaoks ülesanne ei ole lahenduv: näiteks, kui H on arvude hulk, millele vastavad programmid peatuvad. •Poollahenduvus tähendab, et kui X juhuslikult kuulub hulka H, siis me saame seda algoritmiga alati näidata. Kui ei kuulu H-i, siis ei saa alati.
annaabi.ee 
