Theorem(?!)
Uncountably many languages are Turing-recognizable.
Proof
Let
be the set of all infinite languages with infinite complement.
is uncountable [exercise!].
Let L be a language in
, let T be the set of all Turing machines and let W be the set of all words. The three sets L, T and W are countable, as is
T×W.
Define the set A as follows:
A = {(M,w):M accepts w}
A is a subset of T×W
and hence is also countable. In particular, we can find a
bijection f from A to L.
Define the angle-bracket encoding by setting ⟨M,w⟩
to be f((M,w))
. Complete the encoding scheme by encoding objects not of the form (M,w) as elements of the complement of L (this is possible as the complement of L is infinite).
Now, ATM = {⟨M,w⟩:M accepts w} = L
and
ATM
is Turing-recognizable. Therefore our language L is Turing-recognizable.
Hence all languages in the uncountable set
are Turing-recognizable.
