# Why we can't use non-deterministic turing machines in this case?

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.

• 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. – David Richerby Aug 4 '17 at 0:05
• 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. – David Richerby Aug 4 '17 at 0:07
• @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"? – fade2black Aug 4 '17 at 0:09
• 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. – David Richerby Aug 4 '17 at 0:23
• @HaskellFun If you mean $w$'s length is restricted then there are finitey many possibilites. In that case your reasoning works. – fade2black Aug 5 '17 at 8:31