Chapter 9: Turing Machines and Linear Bounded Automata J;\ 295
Proof Let AI be a k-tape TM. After 11 moves of M, the head markers of M]
will be separated by 211 cells or less. (At the worst. one tape movement can be
to the left by 11 cells and another can be to the right by II cells. In this case the
tape headmarkers are separated by 211 cells. In the other cases, the 'gap'
between them is less). To simulate a move of M, the TM M] must visit all the
k headmarkers. If M starts with the leftmost headmarker, M I will go through all
the headmarkers by moving right by at most 211 cells. To simulate the change
in each tape. M] has to move left by at most 271 cells; to simulate changes in
k tapes, it requires at most two moves in the reverse direction for each tape.
Thus the total number of moves by M 1 for simulating one move of M is
atmost 411 + 2k. (211 moves to light for locating all headmarkers, 211 + 2k moves
to the left for simulating the change in the content of k tapes.) So the number
of moves of M] for simulating n moves of M is 11(411 + 2k). As the constant k
is independent of 11, the time taken by M] is O(n:;).
9.7.2 NONDETERMINISTIC TURING MACHINES
In the case of standard Turing machines (hereafter we refer to this machine as
deterministic TM). 8(q). a) was defined (for some elements of Q x n as an
element of Q x r x {L R}. Now we extend the definition of 8. In a
nondetemlinistic TM. 8(ql, a) is defined as a subset of Q x r x {L R}.
Defmition 9.5 A nondeterministic Turing machine is a 7-tuple (Q, L r. 8, qo.
b. F) where
1. Q is a finite nonempty set of states
2. r is a finite nonempty set of tape symbols
3. b E r is called the blank symbol
4. L is a nonempty subset of 1. called the set of input symbols. We
assume that bEL.
5. qo is the initial state
6. F r;;;; Q is the set of final states
7. 8 is a partial function from Q x r into the power set of Q x r x
{L. R}.
1Vote: If q E Q and x E rand 8(q. x) = {(ql. :\'), D 1 ). (q:;, .\':;, D:;) . ...,
(q", )'11' Dill) then the NTM can chose anyone of the actions defined by
(qi' )'i, DJ for i = 1. 2..... 11.
We can also express this in terms of f- relation. If 8(q. x) = {(qi, )ii, DJI
i =1. 2.... , 11} then the ID zq.nv can change to anyone of the 11 IDs specified
by the l1-element set 8(q. x).
Suppose 8(q, x) = {(q], .\'1, L). (q:;, ":;. R). (Q3, \'3, L)}. Then
or
or
Proof Let AI be a k-tape TM. After 11 moves of M, the head markers of M]
will be separated by 211 cells or less. (At the worst. one tape movement can be
to the left by 11 cells and another can be to the right by II cells. In this case the
tape headmarkers are separated by 211 cells. In the other cases, the 'gap'
between them is less). To simulate a move of M, the TM M] must visit all the
k headmarkers. If M starts with the leftmost headmarker, M I will go through all
the headmarkers by moving right by at most 211 cells. To simulate the change
in each tape. M] has to move left by at most 271 cells; to simulate changes in
k tapes, it requires at most two moves in the reverse direction for each tape.
Thus the total number of moves by M 1 for simulating one move of M is
atmost 411 + 2k. (211 moves to light for locating all headmarkers, 211 + 2k moves
to the left for simulating the change in the content of k tapes.) So the number
of moves of M] for simulating n moves of M is 11(411 + 2k). As the constant k
is independent of 11, the time taken by M] is O(n:;).
9.7.2 NONDETERMINISTIC TURING MACHINES
In the case of standard Turing machines (hereafter we refer to this machine as
deterministic TM). 8(q). a) was defined (for some elements of Q x n as an
element of Q x r x {L R}. Now we extend the definition of 8. In a
nondetemlinistic TM. 8(ql, a) is defined as a subset of Q x r x {L R}.
Defmition 9.5 A nondeterministic Turing machine is a 7-tuple (Q, L r. 8, qo.
b. F) where
1. Q is a finite nonempty set of states
2. r is a finite nonempty set of tape symbols
3. b E r is called the blank symbol
4. L is a nonempty subset of 1. called the set of input symbols. We
assume that bEL.
5. qo is the initial state
6. F r;;;; Q is the set of final states
7. 8 is a partial function from Q x r into the power set of Q x r x
{L. R}.
1Vote: If q E Q and x E rand 8(q. x) = {(ql. :\'), D 1 ). (q:;, .\':;, D:;) . ...,
(q", )'11' Dill) then the NTM can chose anyone of the actions defined by
(qi' )'i, DJ for i = 1. 2..... 11.
We can also express this in terms of f- relation. If 8(q. x) = {(qi, )ii, DJI
i =1. 2.... , 11} then the ID zq.nv can change to anyone of the 11 IDs specified
by the l1-element set 8(q. x).
Suppose 8(q, x) = {(q], .\'1, L). (q:;, ":;. R). (Q3, \'3, L)}. Then
or
or