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 , q₀, B, F), where
Q is the finite set of states,
G is the finite set of allowable tape symbols,
B, a symbol of G , is called blank,
S , a subset of G not including B, is the set of input symbols,
d is the next move function, a mapping from Q ´ G to Q ´ G ´ {L, R} (d may however be undefined for some arguments),
q₀ 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
description" (ID) of the Turing machine M by a₁qa₂. Here, q, the current state of M, is in Q; a₁a ₂ 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 a₁a₂).

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

We define a move of a Turing machine (TM) M as follows:
Let X₁X₂ … X_i-1 q X_i … X_n be an ID.
Suppose d (q , X_i) = (p, Y, L), where if i – l = n, then X_i 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
X₁X₂ … X_i-1 q X_i … X_n X₁X₂ … X_i-2 p X_i-1Y X_i+1 … X_n …….. (1)

However, if any suffix of X_i-1Y X_i+1… X_n is completely blank, that suffix is deleted in (1). Alternatively, suppose
d (q, X_i ) = (p, Y, R), then we write,
X₁X₂ … X_i-1 q X_i X_i+1… X_n X₁ X₂ … X_i-1 Y p X_i+1 … X_n ……… (2)

Note that in the case i-1 = n, the string X_i X_i+1… X_n 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 q₁, …, q₅, where q₁ is the initial state and q₅ 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
	B	0	1
® q1	1Lq2	0Rq1	__
q2	BRr3	0Lq2	1Lq2
q3	__	BRq4	BRq5
q4	0Rq5	0Rq4	1Rq4
	0Lq2	__	__

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 0q₁0B 00q₁B 0q₂01 q₂001 q₂B001 Bq₃001 BBq₄01 BB0q₄1 BB1q₄B
BB010q₅ BB01q₂00 BB0q₂100 BBq₂0100 Bq₂Bo100 BBq₃0100 BBBq₄100 BBB1q₄00
BBB10q₄ 0 BBB100q₄B BBB1000q₅B BBB100q₂00 BBB10q₂000 BBB1q₂0000 BBBq₂10000
BBq₂B10000 BBBq₃1000 BBBBq₅0000