written 8.5 years ago by |
Let C be a set of languages. Consider the language $L_c$ defined as follows
$L_c = {{M} | L {M} ∈ C}.$
Then either $L_c$ is empty, or it contains the descriptions of all Turing machines, or it is undecidable.
Proof:
Suppose towards a contradiction that for same class C the language $L_c$ is not empty, it does not contain the descriptions of all Turing machines, and it is decidable.
Then $L_c$ is also not empty, not containing all Turing machines, and decidable.
Suppose that ∅ 6∈ C, otherwise apply the argument below to $L_c$ instead of $L_c$
Let $M_{in}$ be a machine such that $M_{in}$ is in $L_c$.
We will show that the Acceptance problem is decidable, and so we will reach a contradiction.
Given an input ({M}, w) for the Acceptance problem, we constract a new Turing machine M_w that does the following: on input x, $M_w$ first simulates the behaviour of M on input w and
- If M on input w loops, then so does $M_w$;
- If M on input w rejects, then so does $M_w$;
- If M on input w accepts, then M_w continues with a simulation of M_in on input x.
In summary:
If M accepts w, then $M_w$ behaves like $M_{in}$, and $M_w$ accepts an input x if and only if $M_{in}$ does. In other words, $L(M_w) = L(M_{in}) ∈ C \ \ \ \ and \ \ so \ \ {M_w} ∈L_c$;
If M does not accept w, then $M_w$ does not accept any input, and L $(M_w) = ∅ ∈ C$, which implies ${M_w} ∈ L_c$.
We have proved that ({M}, w) ∈ A if and only if ${M_w} ∈ L_c$, and so A would be decidable if $L_c$ were decidable. We have reached a contradiction.