why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable?

I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case decidable and $L=\emptyset$ especially finite and decidable.

I know we cannot find an algorithm but every TM has a language and we even if we don't it, we know it is decidable.

Can someone help me where I do have a misunderstanding?

  • $\begingroup$ Can you prove your claim step by step very slowly? By "very slowly", I mean nothing beyond definitions and known theorems and syllogism in every step. $\endgroup$ – John L. Jan 23 '19 at 18:46
  • $\begingroup$ I cannot proof my claim, it is just an idea. I claim L(M) always decidable if we know L(M), because as I said it contains all words the TM M accepts. So L is empty in my consideration. So I know this is false, but why? Where is my fallacy? $\endgroup$ – Marc Jan 23 '19 at 19:00

You're very close!

The key is the difference between recognizable and decidable.

A language $R$ is recognizable if we can build a TM $T$ such that $L(T) = R$. In other words, there's a Turing machine that accepts exactly those strings in the language—and for strings not in the language, it might halt in a non-accepting state (i.e. it might reject), or it might run forever without halting (i.e. it might diverge).

A language $D$ is decidable if we can build a TM $T$ such that $L(T) = D$, and $T$ rejects (halts in a non-accepting state) on strings not in $D$.

It turns out that a whole lot of languages are recognizable but not decidable. The language $H_0 = \{ \langle M \rangle | M \textrm{ halts on empty input} \}$ is undecidable (this is the Empty-Input Halting Problem), but $H_0$ can be recognized by the following procedure (call it $RH$):

Simulate $M$ on empty input. If it ever halts, accept.

Now we have a Turing machine whose language, $L(RH) = H_0$, is undecidable! Which means the property in question is non-trivial, so by Rice's Theorem that property is undecidable.

| cite | improve this answer | |

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.