Vyučující: Antonín Kučera (zřejmě nemá webové stránky?)
Přednáška bez cvičení povinná pro «teoretické» obory I1 a I4. (I2, I3 mohou místo této a Složitosti I absolvovat ZákladySložitostiAVyčíslitelnosti.)
Povídání o historii a souvislostech, definice Turingova stroje (stejně jako na přednášce Automaty A Gramatiky), obecné povídání o Turingově stroji. První asi čtyři přednášky se budou věnovat Turingovu stroji a rekurzivním funkcím, než se přikročí k «hlavní» látce. Tento úvod se nezkouší, ale hlavně Turingovy stroje se používají v další látce v důkazech. Materiály viz zdroje níže.
na KTIML jsou poznámky zpracované Ladislavem Strojilem, pokrývají látku po prvních čtyřech přednáškách (tj. bez «úvodu»).
Matfyz Wiki poskytuje poměrně bohaté info o předmětu.