Theory of Computation: Lecture 6

Theory of Computation: Lecture 6. The main topics covered in this lesson include: prove the equivalence of enumerators and TMs; dovetailing; definition of algorithm; the Church-Turing thesis; encodings; Hilbert’s 10th problem; Matijasevic’s theorem;...