O'Reilly logo

Introduction to Automata Theory, Formal Languages and Computation by Shyamalendu Kandar

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

9

Variations of the Turing Machine

Introduction

Till now, we have discussed about the Turing machine with a single head and a single tape. It has been clear from the given examples that the Turing machine is a powerful computational machine. But, for some cases, it may seem that the Turing machine takes a lot of time for computation, and it is complex. To understand the computational power of the Turing machine and to reduce the time complexity, researchers have proposed different models of the Turing machine. These models have given us freedom to use a suitable machine wherever applicable to solve a variety of problems by the Turing machine. It can be proved that, computationally, all these Turing machines are equally powerful. That is, what ...

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