Sissejuhatus infotehnoloogiasse eksamikonspekt
suurem kui reaalarvude hulk.
Peatumisprobleem, selle lahendamatuse idee:
Kontrollime, kas etteantud programm jääb seisma.
Kui while ega rekursiooni pole, siis peatub. While korral interpretaator käima, lihtsamate
korral saame teada, raskemate puhul ei tea, kas peatubki.
3n + 1 Collatz conjecture:
Alati on peatunud, aga kuna arve on lõpmatult palju, siis ei saa kindel olla, et pole olemas
olukorda, kus ta ei peatuks. Saaks tõestada matemaatiliselt, aga keegi pole osanud.
Haltanswerer ei ole võimalik kirjutada, või kui saaks, siis oleks maailm
vastuoluline. (Pythoni Nasty(Nasty) näide).
Keerukus on funktsioon f, mis seab andmete mahule n vastavusse algoritmi sammude
arvu (ajaline keerukus) või kasutatava mälu mahu (mahuline keerukus)
• Algoritmi keerukus on põhioperatsiooni(de) arvu sõltuvusfunktsioon K(n)
sisendi(te) suurusest n. Põhioperatsioon on midagi, mis on riistvaras tehtav
annaabi.ee 
