The Turing Machine (TM), introduced by Alan M. Turing through his landmark paper: “On Computable Numbers with an Application to the Entscheidungsproblem”, is the foundation of the Theory of computation. This chapter introduces the TM Model, explains its working principle, its configurations, computations, and language acceptability, and shows that TM also accepts the languages accepted by finite automata and by Pushdown automata. Solutions to the number of standard problems of formal languages and computations have been illustrated through simple examples. The complexity of language recognition as well as of simple arithmetic has been illustrated. The Turing Machine is an algorithm, hence its analogy with modern computers has been convincingly justified. Finally, the Church-Turing thesis and its role in computability conclude that the Turing Machine is the ultimate computing machine. The Post machine, which performs the same functions as a TM, except that its instructions are quadruples against TMs quintuple format, has been briefly introduced. The chapter ends with a discussion on computation beyond the Turing limit, followed by a number of self-review questions, and exercises of varying difficulty levels.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Turing Machine and Computability

  • K. R. Chowdhary

摘要

The Turing Machine (TM), introduced by Alan M. Turing through his landmark paper: “On Computable Numbers with an Application to the Entscheidungsproblem”, is the foundation of the Theory of computation. This chapter introduces the TM Model, explains its working principle, its configurations, computations, and language acceptability, and shows that TM also accepts the languages accepted by finite automata and by Pushdown automata. Solutions to the number of standard problems of formal languages and computations have been illustrated through simple examples. The complexity of language recognition as well as of simple arithmetic has been illustrated. The Turing Machine is an algorithm, hence its analogy with modern computers has been convincingly justified. Finally, the Church-Turing thesis and its role in computability conclude that the Turing Machine is the ultimate computing machine. The Post machine, which performs the same functions as a TM, except that its instructions are quadruples against TMs quintuple format, has been briefly introduced. The chapter ends with a discussion on computation beyond the Turing limit, followed by a number of self-review questions, and exercises of varying difficulty levels.