MAT4: A Taste of Computability and Complexity for Mathematicians

Course Tutor

• Luca Aceto

Course Material

• Course description
• A Note on Rice's Theorem by Hans Hüttel
• Lecture 1
• Lecture 2
• Lecture 3
• Lecture 4
• Lecture 5

Links of Course Related Interest

• Alan Turing in the Encyclopaedia Britannica
• The Alan Turing Home Page
• Turing's World: A book on Turing machines that comes with a program that allows one to design and debug Turing machines.
• Some lectures on Turing Machines from Regina University, Canada.
• Bibliographic Database for Computability Theory
• Stephen Cole Kleene in the Encyclopaedia Britannica.
• Goedel's Incompleteness Theorems in the Encyclopaedia Britannica.
• NP-completeness in the Encyclopaedia Britannica.

• David Matz
• Gerald Pienkowski
• Erol Barbut
• David Woodruff

Look also here for a nice Turing Machine simulator written in Java. (Many thanks to Thomas Rask Thomsen for providing this one!)