programmi sisend ja seismajäämise tuvastamise kriteerium • Juhuslikkust ei ole: Malemäng käib täpselt reeglite järgi, sorteerimisel ei toimu juhuslikke muutusi massiivis, programm ei tee juhuslikke tegevusi. Iga täpselt formuleeritud probleemi (matemaatika- ja programmeerimisprobleemid) jaoks ei leidugi lahendavat algoritmi. Vähe sellest: kui võtta „juhuslik“ probleem, siis tõenäosus, et lahendav algoritm leidub, on lõpmatult väike. Intuitiivne seletus lahendamatusele: Saab näidata, et erinevaid probleeme on lõpmatult rohkem, kui erinevaid algoritme. Kuna probleeme on lõpmatult rohkem kui algoritme, siis iga probleemi jaoks lihtsalt ei jätku lahendavat algoritmi. Probleeme ei saa olla rohkem kui täisarve (st on sama palju või vähem): Iga Pythoni programm on string (aga iga string ei ole Pythoni programm). Iga string koosneb järjestikustest baitidest, iga bait vahemikus 0-255. Iga string vastab ühele täisarvule
Eeldame, et vaatame ainult probleeme, mis on täpselt ja üheselt kirjeldatud ja kus on lahendamiseks olemas piisavalt infot (a la travelling salesman, malemäng jne) Selgub, et iga täpselt formuleeritud probleemi jaoks ei leidugi lahendavat algoritmi! Vähe sellest: kui võtta “juhuslik” probleem, siis tõenäosus, et lahendav algoritm leidub, on lõpmatult väike! Intuitiivne seletus lahendamatusele Saab näidata, et erinevaid probleeme on lõpmatult rohkem, kui erinevaid algoritme. Kuna probleeme on lõpmatult rohkem kui algoritme, siis iga probleemi jaoks lihtsalt “ei jätku” lahendavat algoritmi. Kuidas seda 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)
.Uuritakse, millistele ülesannetele on algoritme, millistele ei .Uuritakse, mis ülseande lahendamine taandub teisele ülesandele .Uuritakse lahendumis, poollahendumist, kreatiivseid hulki jne jne .Uuritakse lõpmatuse struktuuri, mis on kirjeldamatult keeruline .Uuritakse lahendumise struktuuri, mis on kirjeldamatult keeruline .Uuritakse loogikaklasside lahendumise taandumist muudele ülesannetele ..... ITK 2007, Kalev Pihl Sissejuhatus informaatikasse 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
annaabi.ee 
