Formal Languages and Computability (INF3, Autumn'05)
Lecture 12
Main topic:
Mapping reducibility
Lecture Plan
computable functions
formalizing mapping reducibility
further examples of undecidable problems
summary
Reading
Section 5.3 (210-214)