Every non deterministic TM has an equivalent deterministic TM.

Question

The following picture illustrates this theorem:

But I could not understand from where the numbers of the third tape come, could anyone explain this for me please?

Thanks!

Answer 1

Recalling the definition of an NDTM, the machine we are trying to simulate will compute an infinitely expanding tree of computations, where the root is the initial state and the children of each node are the result of applying a nondeterministic instruction (which maps a state of the TM to a set of states).

Each of the nodes in this computation graph can be uniquely identified by a prefix code. For example, we could assign the code 13 to the third children of the first children of the root.

The NDTM will accept the input iff any of the states in its computation tree halts in an accepting state. So we can do the following:

Generate every possible prefix code sequentially, and execute the branch of computation that gets you to the node in the computation tree with said code. If the state accepts the input, then the NDTM simulated accepts the input and you are done. If it does not halt, then generate the next prefix and do the same.

The tape where you keep track of what prefix numbers you have generated and visited so far is the address tape in the picture.

One subtlety the proof above glances over is how to determine when the NDTM halts without accepting. For that, we need to keep track of the prefixes assigned to the states that halt without accepting, and only generate prefixes whose parent has not halted yet. This is easily done via a procedure like breadth first search.

For bonus points, notice how this procedure takes exponential time wrt the steps taken by the NDTM. The P!=NP conjecture states that there is no simulation procedure that will allow you to simulate a NDTM in polynomial time.

PS: by state of the TM, I mean both the internal state and the contents of the tape.