[Solved]: Visualizing a Non Deterministic Decider

Problem Detail: 

I know that we can visualize a Non deterministic TM as a TM which splits into multiple copies of itself whenever it sees a non deterministic path (Yes, I also know that this is just a visualization and is usually used by beginners like me for understanding non determistisism).

Further, I also know that a Decider is a TM that halts on all possible inputs.

Now, my question is how can I visualize a Non determistic Decider? Does a non-determistic decider mean a TM where

1. All the copies must halt, (OR)
2. At-least one copy halts.

Kindly explain in detail why so. Thanks.

Asked By : bongubj

Answered By : Vor

For a nondeterministic decider the answer is At-least one "copy" halts on a "yes"/"no" state; copy-paste from another answer:

1. for a Nondeterministic Turing machine (NDTM) processing an input $x$ there can be infinite computations (paths); some of them will halt on the accept state $q_Y$, some will halt on the reject state $q_N$, some will run forever;

2. a string $x$ is accepted by a Nondeterministic Turing machine if at least one of its computations halts on the accepting state $q_Y$;

3. we say that "$M$ accepts $x$ in $m$ steps" if $M$ accepts $x$ and $m$ is the length of the shortest accepting computation on input $x$;

4. a language $L_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$ (this is independent of whether $N$ is a decider or not);

5. the definition of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:

   $T_M(n) = max ( \{1\} \cup \{ m \; : \; $ there is an $x \in L_M$ such that $|x|=n$ and $M$ accepts $x$ in $m$ steps $\})$

6. we say $M$ is a decider if $T_M(n)$ is computable.

See Garey&Johnson, "Computers and Intractability"

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6253