I'm reading Sipser's description of a deterministic Turing machine D that is simulating a non-deterministic one (Page 179, Chapter 3).
3-Tape Diagram of Turing machine D
I'm having trouble understanding the behaviour of the 3rd "address" tape. I know this TM D will explore the computation tree with breadth-first search and it makes sense, but when I go on to read his description of this simulation (below), I can't put it together.
- Initially, tape 1 contains the input $\omega$, and tapes 2 and 3 are empty.
- Copy tape 1 to tape 2 and initialize the string on tape 3 to be $\epsilon$.
- Use tape 2 to simulate N with input $\omega$ 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.- Replace the string on tape 3 with the next string in the string ordering.
Simulate the next branch of N’s computation by going to stage 2.
In step 3, we simulate N with input $\omega$ on simulation tape 2 for one branch of the computation tree. However, when it says to consult the next symbol to make a choice, I assume it is saying if successful that the 'symbol' transitions N and moves D deeper into the computation tree?
To make myself a bit more clear, Sipser wrote:
To every node in the tree we assign
an address that is a string over the alphabet $T_b$ = {1, 2, …, b}.
We assign the address 231 to the node we arrive at by starting at the root, going to its 2nd child,
going to that node’s 3rd child, and finally going to that node’s 1st child.
So why exactly in step 4, do we replace the string on tape 3 as opposed to appending? Wouldn't we lose our position in the computation tree if we simply replaced the string, as there will no longer be a queue for the breadth first search.
Also, I'm not entirely sure if I'm interpreting 'next string' and 'string ordering' properly. Are they referring to the next address string obtained from the child nodes?
Best Answer
I found Sipser's book and read that part (I, myself, was interested to find out the proof to that theorem). In the version of the book I found, in the step $4$, it is written that we replace the string on tape $3$ with the lexicographically next string.
So, if I understand it correctly, basically, at each step we start over with step $2$ (copying tape $1$ to tape $2$), than, on tape $3$, we take all possible strings (and by that, I mean all possible choices that the Non-Deterministic TM $N$ has). The answer to the question "So why exactly in step $4$, do we replace the string on tape $3$ as opposed to appending?" : my guess is that it's easier to replace a string than to append it, because you would need to add in binary, but don't take my word for it.
Hope this helps you!