12.1INTRODUCTION
We have discussed so far comperatively small and simple classes of languages which are regular
languages and context free languages and their corresponding automatons FA’s and PDA’s
respectively. These automatons are not capable to stores no more than a fixed amount of
information and simultaneously the information can be retrieved only in accordance of LIFO
fashion during activation (live) of the machine. So in totality these modules provide a ‘limited
view of computation’.
Thus, the question arises, what class of language is defined by any computational model.
In general we ask about the capability of the machine or automaton.
Now we extend the approach of computation and discuss a more general model of com-
putation. An abstract machine called Turing Machine is an accepted form of ‘general model of
computation’. We may hypothetically assume that Turing Machine is flexible to store enor-
mous amount of information and also has enormous computing power. So, particular this model
can accommodate the idea of stored program machine like a computer and that is analogous to
the working of human brain. This hypothetical model of computation provides the basis for the
computers.
In 1936, Allan M. Turing proposed a machine known as Turing Machine as a ‘general
model of any possible computation’. To say that any possible algorithm procedure that can be
imagined or immerged by humans can be carried out by some Turing machine. Conversely,
Turing machine provides the way to implement all algorithmic procedures (theoretically). This
hypothesis is known as Church thesis or Church—Turing Thesis.
12.2BASIC FEATURES OF A TURING MACHINE(TM)
Allan Turing literally proposes a human like Computer. A human has a pen and paper and
solve the problem in discrete and isolated computational steps like FA/PDA, it has finite set of
states corresponding to possible ‘states of mind’. In Turing Machine the paper is replaced by
the linear tape of infinite length (whose left boundary is known but no right boundary). Tape
is divided into cells that can hold one symbol at a time.
Tape cells contains symbols of two types,
- First, symbols those are from the list of the set of ‘input symbols’. (so it is a input
device) - Second, ‘tape symbols’ are those symbols that are used for replacing the input symbols
during computation. (it is a output device because the string of tape symbols left on
the tape at the end of computation will be the output generated by TM)
12
Introduction to Turning
Machine
334