Formal Languages and Computability (INF3, Autumn'05)
Lecture 8
Main topic:
Computability Theory: Turing machines
Lecture Plan
- informal introduction; Church-Turing thesis
- formal definition of a Turing machine and its computation
- Turing-recognizable languages
- Turing-decidable languages
Reading