# Language of TM is Undecidable

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?

• 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. Jan 23 '19 at 18:46
• 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?
– 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.