I am reviewing some Turing machine material...and I come across this

the set of all programs are countable (convert them into binary string, each of which represent an integer) whereas the set of all languages over {0,1} are not

I know that the set of all possible words(call it X) over {0,1} (this is the same as set of all binary string) is countable...but the set of all languages over {0,1} isn't it the power set of X, ie the set of all subset of X?

I also know that for an finite set, order of power set of X is $2^{|X|}$, so are we saying that $2^{\infty} \gt \infty$? How can I distinguish relationship between infinity in general? For instance, we have on the contrary: 2*\infty = \infty since set of all positive even integers has the same cardinality all positive integers...

I feel like this has something to do with the infinite set theory, and the prove I saw is the diagonalization argument which I am still having trouble digesting, does there exist better proofs?


Strings have finite length, and programs are of finite collections of strings. While languages don't have that restriction. Cantor's diagonalization doesn't work when everything is finite. Try to see why you need infinite positions to carry that through and things will become clear.

Also, see Cantor's theorem on power sets set and the continuum hypothesis. You will see infinities are of different orders, for example, there are more real numbers than natural numbers. In fact if you let $n_0 =|\mathbb{N}|$ and $n_1 =|\mathbb{R}|$, then using that $2^{\mathbb{N}}$ is in bijective correspondence with $\mathbb{R}$, you can say that $2^{n_0} = n_{1}$. There's actually a hierarchy of infinities that you can build in similar manner.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.