First Assignment: For Wednesday read all of Sections 0.1 and 0.2 carefully, and carefully look through all of Exercises 0.1 through 0.8. Work any of these exercises that seem difficult to you. On Wednesday, we’ll discuss any of this material or these exercises that you have questions about, as well as any questions you have about Monday’s lecture. I hope also on Wednesday to discuss in class some of the material in Sections 0.3 and 0.4 (on proofs), and to discuss the Exercises 0.10 and 0.11, so look this material over too. Finally, if time permits (and I doubt that it will), we’ll begin talking a little about the material in Chapter 1 on finite automata, so you might try beginning reading in this chapter as well. Surely you should do an initial reading of Section 1.1 before the Friday class.

An exercise on proofs, modeling programming languages, and strange conclusions: Choose a reasonable and general purpose programming language, and for this language, we’ll say that a program, P, defines a positive integer n, if

1. P takes no input
2. Upon execution, P halts after some period of time, but before halting, P prints out the integer n (say in decimal notation), and P halts without printing out anything else.

(Clearly, with this as a definition, every program defines at most one integer.)

Note that some programs can be much shorter than the integers that they define. (Give an example.)

Here are some (but not all) reasonable assumptions about programs:

1. Every program has a length (e.g., the number of characters in the program), and this length is always a positive integer.
2. There is a subroutine, which, given a program, P, as input, calculates the length of P, (which we denote by |P|). E.g., just count the total number of characters in P.
3. There are only finitely many programs of any given length.

(Explain why, with these assumptions, that the set of all programs whose length is at most 10,000, can define at most 10,000 integers.)

Just how clever can programs be about understanding what other programs do? Would it be possible to build a program, call it SHORTEST(y), which takes as input a positive integer, n, which when read into the variable y, and then executed, produces a shortest program, call it SHORTEST(n), that defines n? (I.e., SHORTEST produces a shortest program SHORTEST(n), which, when it in turn is executed, does nothing but write out the integer n, but which is a shortest program which will do this.)

Suppose we had such a program, SHORTEST(y). If we had such a program, we could then use SHORTEST(y) as a subroutine in the following collection of programs. One program, call it STRANGE(m ), for each positive integer m, as described by the following schemata:

STRANGE(m):
   Begin
      y := 0
      Repeat
         y := y + 1
         Find SHORTEST(y)
         z := | SHORTEST(y)|
      Until z > m
      Write y
   Halt

Explain the following conclusions:

1. For every positive integer m, the program STRANGE(m ) actually halts.
2. For every positive integer m, the shortest program which can write the positive integer written by STRANGE(m ) must have a length greater than m.
3. For most reasonable programming languages, there is a constant, c, (independent of m), such that | STRANGE(m )| < c + log(m)

Conclude from b) and c) that the alleged subroutine (program), SHORTEST(y), cannot possibly exist. I.e., there can be no program (no algorithm) that given an integer m finds the shortest program which simply outputs nothing but the integer m.

If you find this interesting, you might go to the library, and in the section on philosophy, find a book which discusses logical paradoxes. The paradox known as Richard’s paradox is a prototype for this exercise.