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 ...
Get Formal Languages and Automata Theory 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.
