Unit-5
Section outline
-
Turing Machines and Recursive Function Theory : Basic Turing Machine Model, Representation of
Turing Machines, Language Acceptability of Turing Machines, Techniques for Turing Machine
Construction, Modifications of Turing Machine, Turing Machine as Computer of Integer Functions,
Universal Turing machine, Linear Bounded Automata, Church’s Thesis, Recursive and Recursively
Enumerable language, Halting Problem, Post’s Correspondance Problem, Introduction to
Recursive Function Theory.