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?