626 Advanced Theory of Computation and Computability
In-depth study of concepts related to computability - Chomsky hierarchy - Turing machines – Computability - Decidability - Nondeterministic automats, recursive function theory - Theory of complexity and complexity classification.
Course Plan
PART I : Guided Lectures delivered by Me (5 weeks): State of the art.
1. Introduction to Challenges in Theoretical Computer Science
2. Reviewing basics of TOC: Automata+Computability +Complexity
3. Chomsky hierarchy
4. Recognizability Vs Decidability
5. Complexity
PART II : Students prepare presentations on a topic (5 weeks) from selected state of the art problems in :
1. Complexity, computability and reducibility.
2. Kolmogorov complexity and Solomonoff’s theory of inductive inference applied to Turing Machines. (Soler-Tuscano et al., 2014)
3.Infinite time TMs of Hale.
4. Quantum computers and erasability (Neal Anderson)
PART III: student selects a computational challenge of current interest and contributes to it.
Evaluation:
Midterm 30% (week 7)
Presentation 15%
Assignments 15%
End of semester written exam 40%