Previous | Next |
To obtain a 1-1 correspondence with the natural numbers you can think of first sorting the sentences according to their length, and sorting sentences of the same length in lexicographical order.
The above holds for natural and programming languages.
Think about what follows from these considerations, and from the fact that the cardinality of the set of functions from the natural numbers to the natural numbers is strictly greater than the cardinality of the set of natural numbers.
In particular, what follows about the expressive power of your favourite programming language? (Write a paragraph or two).