Computers and Reality - Cognitive Science 110 - Spring 2007

1. Let B be the set of all functions from N to the set {0,1}.
   This means B is the collection of all functions whose domain is N and whose value ("output") is always either 0 or 1. Here are two examples:
   

   f(x) = {

   1        if x is odd 0        otherwise

   g(x) = {

   1         if  x < 5 0        otherwise

   1. Show that B is infinite by giving infinitely many different functions that are in B.
   2. Show that B is uncountable. (Hint: use a diagonalization argument similar to the one in the last homework assignment).
2. Let S be the set of all finite strings of lower-case letters in the English alphabet.
   Here are a few examples:  abc ;  xyzaabbxp;  hello ; etc.
   Note that strings of infinite length (such as "ababab...") are not in S; only strings of finite length are allowed.
   1. Show that S is infinite by giving infinitely many different strings that are in S. ("S is infinite" means S contains infinitely many different strings.)
   2. Show that S is countable. (Hint: carefully define an ordering similar to the ordering we put on URM programs).
3. Part (b) of this question is difficult to word precisely; do your best to understand it, but if you find it too vague or hard to understand, we'll discuss it in class.
   1. Let T be the set of all finite strings of symbols -- we allow any and all symbols ever used by humans (in all languages), including spaces. Is T countable? Explain why you do or don't think so.
   2. We cannot write all digits of the number pi = 3.14..., but we can give a precise description of pi as "The ratio of the circumference of a circle to its diameter."  Similarly, there are functions that we cannot compute (such as the Busy Beaver function), even though we can precisely describe or define what they are.
      Justify each of the following statements:
      Most real numbers can never be "described" in any form or manner.
      Most functions can never be "described" in any form or manner.
4. Recall that rational numbers are numbers of the form a/b, where a and b are integers and b is not zero (i.e., "rational number" = "fraction"). Note that integers are rational numbers: e.g.,  5 = 5/1;  0 = 0/1. Prove that the set of all rational numbers is countable; do this by either giving a precise algorithm (in English) for how to list all rational numbers in a systematic way, or by putting an order on the set of all rational numbers. (Hint: Try listing twenty or so rational numbers in some "nice pattern", in a way that if you continued your list forever, any given rational number would sooner or later appear on your list.)