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.

up vote 4 down vote accepted

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"

  • Understood. But point 4 dosent make any sense to me. If what you are saying is right, the TC of a NDTM is the TC of the longest copy (in time sense.. i.e longest time taking). Why is that so? If any copy accepted the string, then we can confirm that the NDTM accepts and hence the TC of this copy should be the actual TC rather than TC of some copy which is taking long amount of time – bongubj Oct 23 '12 at 8:03
  • 1
    @bongubj: you take the worst runtime length among the strings of length $n$ in the language $L_M$ decided by $M$ – Vor Oct 23 '12 at 8:08
  • ok. Got it. "The max refers to the max of TC of all n length inputs". "Its not the max of (TC of) all copies for a particular input of n length". – bongubj Oct 23 '12 at 8:55
  • 1
    @bongubj: perhaps it is not clear, but the runtime of machine $M$ on the input $x$ is the length of the shortest accepting path. I.e. when we write "$M$ accepts $x$ in $m$ steps" we implicitly says that there are no other accepting paths shorter than $m$ – Vor Oct 23 '12 at 8:58
  • @bongubj: ok! ... but I think I could better explain it, I'll try to edit the question. – Vor Oct 23 '12 at 9:00

My textbook (Sipser, 3rd edition, 2012, p. 180) explicitly states that "we call a nondeterministic Turing machine a decider if all branches halt on all inputs". So if there are strings on which the NDTM doesn't halt, or if there is even a single computation path on which the NDTM does not halt, it is not a decider. According to this definition, the correct answer would be All the copies must halt

This is in contrast to what Vor answered, but I'm not allowed to comment on his answer. Also, I don't see how Vor answers the question; it only states when a TM recognizes a language or accepts its input. The question was about a TM being a decider, which requires a slightly different behavior.

  • Well, one way to simulate a NDTM N by a DTM D is to have D perform a breath-first search on the computation tree of N. Once an accepting configuration is found, D accepts its input. But for D to be a decider it needs to reject words that are not elements of the language that's being decided. If N does not halt on all branches, D will go on simulating N forever. Looking at the simulation process I'm even more convinced the correct answer should be All the copies must halt. – Martijn Jun 28 '13 at 7:04
  • 1
    Sorry, I still disagree. The existence of a rejecting path for some $x$ does not imply that $w \not \in L(M)$. Only the existence of an accepting path implies $w \in L(M)$. $M$ won't be able to tell, because it needs to simulate all computation paths on $N$ and in doing so it might end up working forever. So once again, only if all branches terminate will $M$ be able to simulate $N$ and decide its language. – Martijn Jun 30 '13 at 14:43
  • @bongubj: Martijn is right, you should change the accepted answer. Martijn: The $T_M(n)$ is computable definition is still correct, nevertheless your definition is standard. – frafl Jun 30 '13 at 16:30
  • Comments work with >= 50 rep, so you can put your comment as a comment after Vor's answer and on the other hand integrate some parts of your comment into your answer and remove the rest. – frafl Jun 30 '13 at 16:39

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.