[Solved]: Visualizing a Non Deterministic Decider

ignougroup
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