Tuesday, August 12, 2008

Turing Machine

In this Chapter, we briefly introduce computable and non-computable functions. For the detailed understanding about this topic
one can refer the books [1,2,3,4].

In the mid of 1930’s, mathematicians and logicians were rigorously trying to define computability and algorithm. In 1934,
Kurt Gödel pointed out that primitive recursive functions can be computed by a finite procedure [that is, an algorithm]. He also hypothesized that any function computable by a finite procedure can be specified by a recursive function. Around 1936, Turing and Church independently designed a "Computing machine" (Later termed as Turing machine) which can carry out a finite procedure.

Turing Machine

In this section we define Turing machines. The basic model of a Turing machine illustrated in the following Figure.1 has a finite
control, an input tape that is divided into cells, a tape head that scans one cell on the tape at a time. The tape has a leftmost cell
but is infinite to the right.

Each cell of the tape may hold exactly one of a finite number of tape symbols. Initially the n leftmost cells, for some finite n ³ 0,
hold the input, which is a string of symbols chosen from a subset of the tape symbols called input symbols. The remaining infinity
of cells each hold the blank, which is a special tape symbol that is not an input symbol.

In one move the Turing machine, depending upon the symbol scanned by the tape head and the state of the finite control,
  1. changes state,
  2. prints a symbol on the tape cell scanned, replacing what was written there, and
  3. moves its head left or right one cell.
Formally, a Turing machine (TM) is denoted by

M = (Q, S , G , d , q0, B, F), where
Q is the finite set of states,
is the finite set of allowable tape symbols,
B, a symbol of G , is called blank,
, a subset of G not including B, is the set of input symbols,
is the next move function, a mapping from Q ´ G to Q ´ G ´ {L, R} (d may however be undefined for some arguments),
q0 in Q is the initial state,
F Í Q is the set of final states.

The functional status of a Turing machines TM at a given instance can be defined and termed as "Instantaneous
" (ID) of the Turing machine M by a1qa2. Here, q, the current state of M, is in Q; a1a 2 is the string in G *,
that is the contents of the tape upto the rightmost nonblank symbol or the symbol to the left of the head, whichever is
the rightmost
. (Observe that the blank B may occur in a1a2).

We assume that Q and G are disjoint to avoid confusion. The tape head is assumed to be scanning the leftmost symbol of a2 or
if a2 = L (the empty string), then the head is scanning a blank.

We define a move of a Turing machine (TM) M as follows:
Let X1X2 … Xi-1 q Xi … Xn be an ID.
Suppose d (q , Xi) = (p, Y, L), where if i – l = n, then Xi is taken to be B. If i = l, then there is no next ID, as the tape head is
not allowed to fall off the left end of the tape. If i > 1, then we write
X1X2 … Xi-1 q Xi … Xn X1X2 … Xi-2 p Xi-1Y Xi+1 … Xn …….. (1)

However, if any suffix of Xi-1Y Xi+1… Xn is completely blank, that suffix is deleted in (1). Alternatively, suppose
(q, Xi ) = (p, Y, R), then we write,
X1X2 … Xi-1 q Xi Xi+1… Xn X1 X2 … Xi-1 Y p Xi+1 … Xn ……… (2)

Note that in the case i-1 = n, the string Xi Xi+1… Xn is empty, and the right side of (2) is larger than the left side.

If one ID results from another by some finite number of moves, including zero moves, then we say the ID's are related and one ID
yields the other ID.

We give the definition of in the form of a table called the transition table.
If d(q, a) = (), we write abg under "a-column" and "q-row". So if we get abg in the table, it means that a is written in
the current cell, b gives the movement of the head L or R and g denotes the new state into which the Turing machine enters.

Consider, for example, a Turing machine with five states q1, …, q5, where q1 is the initial state and q5 is the (only) final state.
The tape symbols are 0,1 and B. The transition table given in the following Table 1 describes d.

Table 1: Transition Table of a Turing Machine

Present state

Tape symbols




® q1



















The initial state is marked with ® and final state with .

Computation of a Turing machine M is a sequence of ID’s such that an ID in a sequence yields its next ID under the definition
of transition function d .

We give below the computation of the above TM on the input string 00B.

Q100B 0q10B 00q1B 0q201 q2001 q2B001 Bq3001 BBq401 BB0q41 BB1q4B
BB010q5 BB01q200 BB0q2100 BBq20100 Bq2Bo100 BBq30100 BBBq4100 BBB1q400
BBB10q4 0 BBB100q4B BBB1000q5B BBB100q200 BBB10q2000 BBB1q20000 BBBq210000
BBq2B10000 BBBq31000 BBBBq50000

No comments: