Formal Languages and Computability (INF3, Autumn'05)
Lecture 9
Main topic:
Church-Turing thesis and the notion of an algorithm
Lecture Plan
- Robustness of Turing machines (bi-directional TM,
multitape TM, nondeterministic TM, enumerators and other models)
- Turing machines as algorithms
Reading