Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning is not working.

Problem Given a context free grammar $G$, does there exists a word $w∈Σ^∗$ such that $w^4∈L(G)$ ?

My reasoning: Lets show Turing machine which decide this problem. Let machine guesses some word $w$ (it is possible because word is finite and $Σ$ is finite) and check if (using CYK algorithm) $G$ generates $w^4$.

I totally don't understand why this approach doesn't work. After all, non-determinism is about guessing...


Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In other words, the TM always halts.

In your approach the TM machine has to guess infinitely many strings and check if their forth power belongs to $L(G)$. A nondeterministic Turing machine cannot check infinitely many strings in finite amount of time.

Decidability problems efficiently solved by non-deterministic Turing machines are also solved by deterministic Turing machines. In other words, their computational powers are equivalent.

  • 1
    $\begingroup$ Indeed, a nondeterministic TM can't make infinitely many nondeterministic choices in finite time: at each state, there are only finitely many possible actions -- say at most $k$ of them. So, after $t$ steps, you can only explore $k^t<\infty$ possibilities. $\endgroup$ – David Richerby Aug 4 '17 at 0:05
  • $\begingroup$ I deleted an "efficiently" from the last paragraph, since the best known deterministic simulations of nondeterministic computations are exponentially slower. Also, your last parenthesis looks like you're claiming $\mathrm{P}\neq\mathrm{NP}$, which we don't know for sure. $\endgroup$ – David Richerby Aug 4 '17 at 0:07
  • $\begingroup$ @DavidRicherby As for your first comment, don't I say the same thing, namely "a nondeterministic TM can't make infinitely many nondeterministic choices in finite time"? $\endgroup$ – fade2black Aug 4 '17 at 0:09
  • $\begingroup$ You say you don't think they can, which sounds uncertain. I'm clarifying that you're right. Also, the words you've put in quotes in your comment aren't a quote from your answer. $\endgroup$ – David Richerby Aug 4 '17 at 0:23
  • 1
    $\begingroup$ @HaskellFun If you mean $w$'s length is restricted then there are finitey many possibilites. In that case your reasoning works. $\endgroup$ – fade2black Aug 5 '17 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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