Chapter 10. Variations of Turing Machines

In Chapter 9, we defined the computability model called “Turing Machine” (TM). This model is one of the most beautiful, simple, and an useful abstract model. We had elaborate discussion of this model through various examples. One can think of variations of the basic model in many ways. For example, one can work with two tapes, instead of a single tape. These models are got by adding extra components and power to the control and hence, appear to be more powerful than the basic model, but they are not. We could also consider some restricted version of the basic model. In this chapter we are considering such variants and discuss their computing capabilities. We note that the power is not increased by adding ...

Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.