O'Reilly logo

Formal Languages and Automata Theory by K.V.N. Sunitha

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

6

Turing Machines

  • Turing machine is a yardstick for computations that can be carried out on a digital computer. Turing machines, first described by Alan Turing in (Turing 1937), are simple, abstract, computational devices intended to help investigate the extent and limitations of what can be computed.

In this chapter, we discuss Turing machines (TMs) and their applications. Turing, writing before the invention of the modern digital computer, was interested in the question of what it means to be computable? Intuitively, a task is computable if one can specify a sequence of instructions which when followed will result in the completion of the task. Such a set of instructions is called an effective procedure, or algorithm, for the task. This ...

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