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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
