2009 June 2 / |j|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u

# Assignment 8

Carleton College CS 254, Fall 2008, Prof. Joshua R. Davis

These problems are not to be handed in. However, you are responsible for this material for our final exam. As always, I am happy to discuss it with you.

A. How many Turing machines are there? How many languages over the alphabet {0, 1} are there? Prove that there are languages over {0, 1} that are not recursively enumerable.

B. In the SKI combinatorial logic system, find a function B (that is, a combination of Ss, Ks, and Is) that performs like this:

B M N P -> M (N P).

Hint: My B uses two Ss and two Ks.

C. In the SKI combinatorial logic system, let

Z = S S K (S (K (S S (S (S S K)))) K).

Show that Z is a fixed point operator. (It is slightly shorter than the standard fixed-point operator Y.)

D. In class we've proved that K(x) is not computable. So the following algorithm for computing K(x) must be wrong. What is wrong with it?

Let M be a Turing machine that immediately halts. Let b be |M| + |#|. As we saw in class, for all strings x, K(x) <= |x| + b. Now let's design a Turing machine N to compute K(x). On input x, N first computes |x| + b. Then N starts trying every bitstring (in lexicographic order) until it finds a description of x; as soon as N finds a description of x, N outputs the length of that description. Because K(x) <= |x| + b, there must be a description of x somewhere in the strings of length less than or equal to |x| + b, so N always halts. Because it tries the strings in order of increasing length, upon halting its tape is always K(x).

E. [I haven't solved this one yet, so I'm not sure how difficult it is.] In class we proved that there exists a constant c such that for all x and y, K(xy) <= 2 K(x) + K(y) + c. Prove that the following statement is false: There exists a constant c such that for all x and y, K(xy) <= K(x) + K(y) + c.