80-150 The Nature of Reason

Summer Two 2001, Dirk Schlimm Homework No. 6 Tuesday, July 10

Reading.
Read TTT, pages 54-61.
Study questions. (4 points)
Answer from TTT, page 49, questions 1 and 2..
The infinite. (6 points)
If a language has only finitely many letters, then the number of sentences that can be formulated in this language is denumerable, i.e., the cardinality of the set of sentences is the same as the cardinality of the set of natural numbers.
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).