Add to ORKGOptimization and decision problems, Reductions, Turing Machine as an acceptor and as an enumerator—Techniques of Turing Machine construction – parallel tracks and storage in control, subroutine Turing Machine, Church-Turing thesis, Variants of Turing Machine – multitape, nondeterministic—their equivalences with other models. Properties of recursively enumerable and recursive sets. Relations between unrestricted grammars and Turing Machines. Linear Bounded Automata —relation with Context Sensitive Languages Enumeration of Turing Machines, existence of undecidable problems, Undecidable problems involving Turing Machines and CFG’s. Universal Turing Machine as a model of general purpose computer, Post Correspondence Problem – Applications, vali...