Programmeerimiskeel
25
Intuitiivne selgitus lahendamatusele
•Selleks näitame:
.Algoritme on sama palju, kui täisarve
.Probleeme on sama palju reaalarve
.Reaalarve on rohkem kui täisarve
ITK 2007, Kalev Pihl
Sissejuhatus informaatikasse
26
Kui palju on algoritme?
•Iga algoritmi saab realiseerida mingis
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,
annaabi.ee 
