Theory of Computation (CS6160) Lecture 05 (Part 2 of 2), Professor Gabriel Robins

Specific topics covered in this lecture: Turing machine enhancements, decidability vs. recognizability, recognition and enumeration, halting problem language is recognizable but not decidable, decidability and lexicographic-order enumerability, building an enumerator from a recognizer, building a recognizer from an enumerator, dovetailing enumeration, avoiding duplicates, parallel enumeration, Chomsky hierarchy, why is it difficult to decide / recognize. sums-of-three-cubes, Diaphantine equations, Hilbert's Tenth Problem, closure properties of decidable and recognizable languages