Why do the definitions of non-deterministic Turing machines look strange?

I read some definitions of the NDTM in several books. Something makes me confused.

Some definitions say that the NDTM $M$ makes an arbitrary choice as to which of its transition functions to apply.

So, if $x \in L(M)$, then $M$ can always guess a branch which leads to $q_{accept}$. And if $x \not\in L(M)$, then $M$ just chooses an arbitrary branch until it enters $q_{reject}$. It seems that $M$ knows the result after reading $x$ because the rule which tells $M$ how to guess depends on whether $x$ is in $L(M)$.

It looks so strange!

Another definitions say that $M$ executes all branches in parallel.

That looks better. And it shows that if $x \in L(M)$, then $M$ halts when it enters $q_{accept}$ at the first time. However, the running time of NDTM is defined as the maximum number of steps that $M$ uses on any branch of its computation on any input. I am not sure if the definitions of the running time of NDTM are equivalent.

• Executing all branches in parallel may be a misleading rule, since a machine that can parallelize the process is much more powerful. – rus9384 Oct 7 '17 at 20:52
• Isn't "Why does this seem strange?" a question about you, rather than a question about Turing machines? – David Richerby Oct 7 '17 at 20:57
• I do not know that it is a question about me (just I think it is strange) or about NDTMs (I do not understand the definitions actually) at the first time. :) – TeamBright Oct 7 '17 at 21:21
• @rus9384 You mean the machine which executes all branches decides more languages or it decides more languages in polynomial time？ – TeamBright Oct 8 '17 at 5:44
• @TeamBright, machine that can have exponentially (of working tape length) many threads is as powerful as alternating TM. – rus9384 Oct 8 '17 at 13:43

Do not think of a non-deterministic machine as a mechanism that actually operates in some fashion. Instead, think of it as a way of making a tree of possibilities: whenever the machine "guesses" or "chooses" a transition, think of that as a node which branches into several further computation trees, one for each transition.

The tree will have many possible paths of execution. We can ask questions like:

1. Is there at least one path that leads to acceptin the input?
2. Do all paths lead to accepting the input?
3. Do more than half the paths lead to accepting the input?

And so on. The usual notion of a non-deterministic machine uses the first point above, i.e., we usually study whether there is any choice of transitions that leads to accepting the input. This is different from trying to devise an actual machine that will make such choices. We just want to know whether the choices exist.

Once you get used to the trees, you can start thinking of such a tree as describing a machine which actually runs. Of course, you need to explain to yourself how the machine chooses a particular path in the tree. You can think of it "guessing the future" or "being lucky" or "running all possibilities in parallel universes and then picking the one that works". It doesn't really matter what story you make up, so long as it fits your intuition and the definition. We're not actually going to build a non-determinstic machine (except if someone can master parallel universes or make a machine that can predict the future).

Basically, a NDTM on input $x$ may have more than one computation branches. If at least one of these branches accepts the input then we say the NDTM accepts the input $x$, otherwise it rejects.

You can consider a NDTM as a finite number computation branches such that branch on input$x$ may halt with accept or reject, or run forever. If at least one branch halts with accept then the NDTM accepts that input no matter other branches halts or run forever. If no branch accepts (halts with in ACCEPT state) then we say the NDTM does not accept the input. And if every branch halts and rejects then we say that NDTM rejects the input.

Do not try look for a real life model of a NDTM. It is just a conceptual computation model which allows to define a complexity class known as $\mathrm{\mathbf{NP}}$ class.

This post has more.

• Thanks for the question you asked and its answers. I just can image that there is an oracle who tells the NDTM which branch it can run. However, whatever it is a hint or a genie who helps the NDTM. she must know the answer at the first time. Why do not she just speak it out? It is a well-defined mathematical model, but it still looks strange because I have not capture the subtleties of nondeterminism. – TeamBright Oct 7 '17 at 20:18
• @TeamBright Consider "many-branch" model of a NDTM. Assume you create $n$ parallel processes which return $0$, $1$ or run forever. So, if at least one process stops and returns $1$ then the whole computation accepts the input, if none of the processes returns $1$ then the NDTM does not accept the input. All other models can be proved equivalent. – fade2black Oct 7 '17 at 20:30
• Do you have a citation of the proof or can you give me a hint? – TeamBright Oct 7 '17 at 20:39
• @TeamBright Unfortunately I do not know about any source which provides such a proof, but it would be a good exercise for you. Just pick two models and try to prove their equivalence. If you get stuck you can always post your question together with your attempt. You simply have to show that one model can simulate another one exactly as we show that a DTM can simulate a NDTM. – fade2black Oct 7 '17 at 20:53