2012 May 26,
Carleton College, Spring 2012
Prof. Joshua R. Davis, , Goodsell 106B, x4473
This assignment is due Wednesday at noon.
A. In Monday's class, we proved (or will prove) 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 c be |M| + |#|. As we saw in class, for all strings x, K(x) <= |x| + c. Now let's design a Turing machine N to compute K(x). On input x, N first computes |x| + c. 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| + c, there must be a description of x somewhere in the strings of length less than or equal to |x| + c, so N always halts. Because it tries the strings in order of increasing length, upon halting its tape is always K(x).
B. Do Problem 6.20.
C. Do Problem 6.21.
D. Do Problem 6.23. (This will be much easier after Monday's class.)