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,
- changes state,
- prints a symbol on the tape cell scanned, replacing what was written there, and
- moves its head left or right one cell.
M = (Q, S , G , d , q_{0}, 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_{0} 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_{1}qa_{2}. Here, q, the current state of M, is in Q; a_{1}a _{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 a_{1}a_{2}).
We assume that Q and G are disjoint to avoid confusion. The tape head is assumed to be scanning the leftmost symbol of a_{2} or
if a_{2} = 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_{1}X_{2 }… 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_{1}X_{2 }… X_{i-1} q X_{i }… X_{n} X_{1}X_{2 }… X_{i-2} p X_{i-1}Y X_{i+1} … X_{n} …….. (1)
However, if any suffix of X_{i-1}Y 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_{1}X_{2 }… X_{i-1} q X_{i} X_{i+1}… X_{n} X_{1} X_{2} … 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_{1}, …, q_{5}, where q_{1} is the initial state and q_{5} 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 | |
® q_{1} | 1Lq_{2} | 0Rq_{1} | __ |
q_{2} | BRr_{3} | 0Lq_{2} | 1Lq_{2} |
q_{3} | __ | BRq_{4} | BRq_{5} |
q_{4} | 0Rq_{5} | 0Rq_{4} | 1Rq_{4} |
| 0Lq_{2} | __ | __ |
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_{1}0B 00q_{1}B 0q_{2}01 q_{2}001 q_{2}B001 Bq_{3}001 BBq_{4}01 BB0q_{4}1 BB1q_{4}B
BB010q_{5} BB01q_{2}00 BB0q_{2}100 BBq_{2}0100 Bq_{2}Bo100 BBq_{3}0100 BBBq_{4}100 BBB1q_{4}00
BBB10q_{4} 0 BBB100q_{4}B BBB1000q_{5}B BBB100q_{2}00 BBB10q_{2}000 BBB1q_{2}0000 BBBq_{2}10000
BBq_{2}B10000 BBBq_{3}1000 BBBBq_{5}0000
No comments:
Post a Comment