Sissejuhatus infotehnoloogiasse eksamikonspekt
Lahendatavad ülesanded:
• Infot on piisavalt: meil on olemas kõik vajalikud aksioomid/programm/täpne
ülesanne, nt: Maleseis ja käigureeglid, täisarvude massiivi sorteerituse kriteerium,
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):
annaabi.ee 
