Unit-3 introduces Turing Machines (TMs) and recursively enumerable (r.e.) languages. The languages defined by TMs, that is, the r.e. sets are the most complex computable sets. Some r.e. sets are undecidable; that is, on certain input the TM may not halt and may loop for ever. Study Rice's theorem on undecidability. Also, there are sets that are not recognizable or not computable in the strongest sense. Regular languages and Context-Free languages are subsets of r.e. sets. The relationship of languages with their processors is shown in the Chomsky Hierarchy

The notes on Mathematical Foundations or the Theory of Computation presented in this unit and others are mainly based on Hopcroft, J., Motwani, R. & Ullman, J. (2007), Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Addison Wesley and Daniel Cohen, (1997), Introduction to Computer Theory, 2nd Edition, John Wiley & Sons, and Sipser, M. (2012) Introduction to the Theory of Computation, Cengage Learning, 3rd edition. Revealing examples are taken from these sources in order to explain mathematical models of computation.     Please click here to go back to the Mathematical Foundations home page .