8
Turing Machine
Introduction
Around 1936, when there were no computers, Alen Turing proposed a model of an abstract machine called the Turing machine which could perform any computational process carried out by the present day’s computer. The machine was named after Turing, and it is called the Turing machine. The Turing machine is the machine format of unrestricted language, i.e., all types of languages are accepted by the Turing machine.
Based on the Turing machine, a new theory called the ‘theory of undecidable problems’ is developed. These types of problems cannot be solved by any computer.
8.1 Basics of Turing Machine
The Turing machine, in short TM, is defined by 7 touples
where
Q : Finite set of states ...
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.
