Simulation of Nondeterministic Turing machine by Multi-tape Turing machie
Definition of Turing machine:
A Turing machine is a 7-tuple, (Q , Σ , Γ , δ , q0 , q Accept , q Reject ), where Q , , Σ , Γ are all finite sets and
1. Q is the set of states,
2. Σ is the input alphabet not containing the special blank symbol ⌴,
3. ,Γ is the tape alphabet, where ⌴ ϵ Γ and Σ ⊆ Γ,
4. δ: Q x Γ → Q x Γ x { L , R } is the transition function,
5. q0 ϵ Q is the start state,
6. q Accept ϵ Q is the acceptance state, and
- q Reject is the reject state, where q Reject ≠ q Accept
Often a few extra symbols are needed to make computation easier. ⌴ is a special symbol which allows the TM to know where its input ends by just searching for a blank.
Definition of Multi-tape Turing machine:
1. A multi-tape Turing machine is like an ordinary Turing machine with several tapes.
2. Each tape has its own head for reading and writing.
3. Initially, the input is written on the first tape, and all the other tapes are blank, with each head at the beginning of the corresponding tape.
4. The transition function is changed to allow for reading, writing, and moving the heads on some or all of the tapes simultaneously.
Formally, the transition function of the Multi-tape Turing machine is represented as
δ: Q x Γk → Q x Γk x { L , R , S }k,
where k is the number of tapes. The expression
δ (q i , a1 , . . . , ak ) = (q j , b1 ,. . . , bk , L , R, . . . , L )
It means that, if the machine is in state q I , and heads 1 through k are reading symbols a1 through ak , the machine goes to state q j , writes symbols b1 through bk , and directs each head to move left or right, or to stay put, as specified.
“Two machines are equivalent if they recognize the same language.” But equivalent does not mean that the two machines have the same speed, efficiency, runtime, feasible to program, steps of computation etc.
Multi-tape Turing machines appear to be more powerful than ordinary Turing machines, but they are no more powerful than single-tape Turing machines. But multi-tape Turing machines are useful because they are a bit easier to program and more useful for some tasks.Every multi-tape Turing machine has an equivalent single-tape Turing machine.
Definition of Nondeterministic Turing machine:
A non-Deterministic Turing Machine allows more than one possible action per given state-tape symbol pair. It has same the power as Deterministic Turing machine. A nondeterministic Turing machine is defined like a standard Turing machine except for the transition function.
d : Q¢ ´ G ® p(Q ´ G ´ {L, R})
Where, Q¢ = Q – {qacc, qrej}.
Figure showing the difference between Deterministic and Non-Deterministic TM in terms of Transition.
In Nondeterministic Turing machine there are several different states it can transition to. As shown in figure above, from state q4 there are three different possible transitions. Upon symbol b
· It can move to state q5 by writing the symbol c and moving the tape head to its right, OR
· it can move to state q6 by writing the symbol d and moving the tape head to its left OR
· it can move to state q7 by writing the symbol c and moving the tape head to its left.
The computation of a Nondeterministic Turing mahcine is a Tree whose branches corespond to different possibilities for the machine.
Nondeterministic TM
Fig State diagram of Non-determnistic TM
Computation history is no longer a linear sequence. It’s a tree.
Fig Computation history of Non-deterministic TM
Outcomes of a Nondeterministic computation
ACCEPT: If any branch of the computation accepts, then the nondeterministic Turing machine will HALT and ACCEPT.
REJECT: If all branches of the computation HALT and REJECT (i.e no branches accept but all computation halts and no infinite computations) then the nondeterministic TM REJECTS.
LOOP: Computation continues forever, but accept is never encountered. These branches in the computation history are infinite.
Fig The path followed by the tree to reach the node whose address is 2322114
A path to any node is given by an Address that is a string over the alphabet
Σb = {1,2, …. ,b}. Where b is the size of the largest set of possible choices given by Nondeterministic TM's transition function. Every node in the tree can have at most b children.
At each step, each symbols in the string tells which choice we took. While simulating a nondeterministic TM using deterministic TM, the deterministic TM has to search the tree looking for ACCEPT by using the Breadth first search algorithm. This strategy explores all branches to the same depth before going on to explore any branch to the next depth. This method guarantees that the deterministic TM will visit every node in the tree until it encounters an accepting configuration.
To examine a node :
· Perform the entire computation from scratch
· The path numbers tell which of the many nondeterministic choices to make at each step of the computation.
· The empty string is the address of the root of the tree.
· Sometimes a symbol may not correspond to any any choice if too few choices are available for a configuration. In that case the address is invalid and does not correspond to any node.
· Some computation will have zero choices. These branches of the nondeterminism die out or halt and reject.
Simulation of Nondeterministic Turing machine by Multi-tape Turing machie
Theorem: Every Nondeterministic Turing machine N has an equivalent deterministic Turing machine D.
Proof: The simulating deterministic TM D has three tapes. By the Theorem proved under Multi-tape TM, this arrangement is equivalent to having a single tape. The machine D uses its three tapes in a particular way, as illustrated in the following figure.
· Tape 1 always contains the input string and is never altered.
· Tape 2 maintains a copy of N's tape on some branch of its nondeterministic computation.
· Tape 3 keeps track of D's location in N's nondeterministic computation tree.
Fig Deterministic TM D simulating nondeterministic TM N
Tape 3 contains a string over Σb. Where Σb = {1,2, …. ,b} and every node in the tree can have at most b children. It represents the branch of N's computation from the root to the node addressed by that string, unless the address is invalid.
1. Initially tape 1 contains the input w, and tape 2 and tape 3 are empty.
2. Copy tape 1 to tape 2.
3. Use tape2 to simulate N with input w on one branch of its nondeterministic computation. Before each step of N consult the next symbol on tape 3 to determine which choice to make among those allowed by N's transition function. If no more symbols remain on tape 3 or if this nondeterministic choice is invalid, abort this branch by going to stage 4. Also go to stage 4 if a rejecting configuration is encountered. If an accepting configuration is encountered, accept the input.
4. Replace the string on tape 3 with the lexicographically next string. Simulate the next branch of N's computation by going to stage 2.
Reference:
· From my cs520 project on Variants of Turing machine
· Introduction to Theory of Computation by Micheal Sipser