Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
