To show that the set of all Turing machines is countable, we first observe that the set of all strings Σ∗ is countable for any alphabet Σ. With only finitely many strings of each length, we may form a list of Σ∗ by writing down all strings of length 0, length 1, length 2, and so on.

The set of all Turing machines is countable because each Turing machine M has an encoding into a string ⟨M⟩. If we simply omit those strings that are not legal encodings of Turing machines, we can obtain a list of all Turing machines.

To show that the set of all languages is uncountable, we first observe that the set of all infinite binary sequences is uncountable. An infinite binary sequence is an unending sequence of 0s and 1s. Let B be the set of all infinite binary sequences. We can show that B is uncountable by using a proof by diagonalization similar to the one we used in Theorem 4.17 to show that R is uncountable.

Let L be the set of all languages over alphabet Σ. We show that L is uncountable by giving a correspondence with B, thus showing that the two sets are the same size. Let Σ∗ = {s1, s2, s3, . . .}. Each language A ∈ L has a unique sequence in B.The ith bit of that sequence is a 1 if s_i ∈A and is a 0 if s_i ̸∈A, which is called the characteristic sequence of A. For example, if A were the language of all strings starting with a 0 over the alphabet {0,1}, its characteristic sequence χA would be
Σ∗={ ε, 0, 1, 00, 01, 10, 11, 000,001, ··· } ;
A={ 0, 00, 01, 000,001,···};
χA= 0 1 0 1 1 0 0 1 1 ··· .

The function f : L−→B, where f(A) equals the characteristic sequence of A, is one-to-one and onto, and hence is a correspondence. Therefore, as B is uncountable, L is uncountable as well.

Thus we have shown that the set of all languages cannot be put into a correspondence with the set of all Turing machines. We conclude that some languages are not recognized by any Turing machine.

–Introduction to the Theory of Computation. 3e, by Michael Sipser

(Some of the symbols didn’t quite come through correctly. Pasting from a PDF is always iffy. The logic, though, should still be fairly clear I think.)