O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required