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  two topic   (5 weeks) from the following :
1. The L-machines ( James Ladyman (theory) + Neal G. Anderson (implementation): What does it mean to say that a physical system implements a computation?
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 eras ability (Neal Anderson)
 
PART III: student selects a computational challenge and contributes to it (Expected publication within 4 weeks.
Evaluation:
Paper 40%
Seminars 30%
End of semester written exam 30%