Computability Theory (SE226)

to undergraduates, School of Software

Textbook

[Cut80] Nigel J. Cutland. Computability: An Introduction to Recursive Function Theory. 1980.

Lectures

Lecture 1. Introduction.

Lecture 2. URM.

Lecture 3. Primitive recursive function.

Lecture 4. Recursive function.

Lecture 5. Turing machine.

Lecture 6. Church-Turing thesis.

Lecture 7. S-M-N theorem.

Lecture 8. Universal program.

Lecture 9. Undecidability.

Lecture 10. Recursive set.

Lecture 11. Recurisve enumerable set.

Lecture 12. Simple set.

Materials

Guoqiang Li
Last modified: Fri, Jan. 30, 2026.