Turing Machines
and Linear Bounded
Automata
In the early 1930s. mathematicians were trying to define effective computation.
Alan Turing in 1936. Alanzo Church in 1933, S.C. Kleene in 1935, Schonfinkel
in 1965 gave various models using the concept of Turing machines, JL-calculus,
combinatory logic, post-systems and p-recursive functions. It is interesting to
note that these were formulated much before the electro-mechanicaVelectronic
computers were devised. Although these formalisms, describing effective
computations. are dissimilar, they tum to be equivalent.
Among these formalisms, the Turing's formulation is accepted as a model
of algorithm or computation. The Church-Turing thesis states that any
algorithmic procedure that can be carried out by human beings/computer can be
carried out by a Turing machine. It has been universally accepted by computer
scientists that the Turing machine provides an ideal theoretical model of a
computer.
Turing machines are useful in several ways. As an automaton, the Turing
machine is the most general model. It accepts type-O languages. It can also be
used for computing functions. It turns out to be a mathematical model of partial
recursive functions. Turing machines are also used for determining the undecidability of certain languages and measuring the space and time complexity
of problems. These are the topics of discussion in this chapter and some of the
subsequent chapters.
For fonnalizing computability, Turing assumed that, while computing,
a person writes symbols on a one-dimensional paper (instead of a twod;rnensional paper as is usually done) which can be viewed as a tape divided
into cells.
One scans the cells one at a time and usually performs one of the three
simple operations, namely (i) writing a new symbol in the cell being currently
277
and Linear Bounded
Automata
In the early 1930s. mathematicians were trying to define effective computation.
Alan Turing in 1936. Alanzo Church in 1933, S.C. Kleene in 1935, Schonfinkel
in 1965 gave various models using the concept of Turing machines, JL-calculus,
combinatory logic, post-systems and p-recursive functions. It is interesting to
note that these were formulated much before the electro-mechanicaVelectronic
computers were devised. Although these formalisms, describing effective
computations. are dissimilar, they tum to be equivalent.
Among these formalisms, the Turing's formulation is accepted as a model
of algorithm or computation. The Church-Turing thesis states that any
algorithmic procedure that can be carried out by human beings/computer can be
carried out by a Turing machine. It has been universally accepted by computer
scientists that the Turing machine provides an ideal theoretical model of a
computer.
Turing machines are useful in several ways. As an automaton, the Turing
machine is the most general model. It accepts type-O languages. It can also be
used for computing functions. It turns out to be a mathematical model of partial
recursive functions. Turing machines are also used for determining the undecidability of certain languages and measuring the space and time complexity
of problems. These are the topics of discussion in this chapter and some of the
subsequent chapters.
For fonnalizing computability, Turing assumed that, while computing,
a person writes symbols on a one-dimensional paper (instead of a twod;rnensional paper as is usually done) which can be viewed as a tape divided
into cells.
One scans the cells one at a time and usually performs one of the three
simple operations, namely (i) writing a new symbol in the cell being currently
277