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

Question

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.

Answer 1

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).

Answer 2

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.