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 ...
Get Introduction to Automata Theory, Formal Languages 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.
