MIT OpenCourseWare http://ocw.mit.edu 6.080 / 6.089 Great Ideas in Theoretical Computer Science Spring 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.� � 6.080/6.089 Problem Set 2 Assigned: Thursday, Feb. 28, 2008 / Due: Thursday, March 13, 2008 1. In 1962, Tibor Rado defined S (n), or the nth “Busy Beaver shift number,” to be the maximum number of steps made by any n-state Turing machine that eventually halts. Here a Turing machine has a two-way infinite tap e with either 0 or 1 on each square, and all tape squares are initially s e t to 0. A “step” consists of writing a 0 or 1 to the current square, moving either left or r ight by one square, and either transitioning to a new state or halting (with all of these decisions determined by the current state together with the symbol on the curre nt squar e ). (a) Show that S (1) = 1. (b) Show that S (2) ≥ 6. [Hint: Try various 2- state Turing machines until you find one that runs for 6 steps before halting.] (c) Show that S (n) grows faster than any computable function. In o ther words, there is no com-putable function C such that C (n) ≥ S (n) for all n. (d) Show that there is not even a computable function C such that C (n) ≥ S (n) for infinitely many n. 2. Given a set of strings L ⊆ {0, 1} ∗ , we say L is computable if there exists a Turing machine that, given as input a s tring x, decides whether x ∈ L. We say L is c.e. (for “computably enumerable”) if there exists a Turing machine M that, when started on a blank tape, lists all and only the strings in L. (Of course, if L is infinite, then M will take an infinite amount of time.) (a) Let HALT be the set of all Turing machines that ha lt when star ted on a blank tape. (Here each Turing machine is encoded as a binary string in s ome reasonable way.) Show that HALT is c.e. [Note: In this and the following problems, you do no t need to construct any Turing machines; just give a convincing argument.] (b) Let L be any c.e. set. Show that L is computable given an oracle that, for any string x, decides whether x ∈ HALT . (c) Show that a set L is computable if and only if L and L ar e both c.e. (Here L is the complement of L: that is, the set of all x ∈ {0, 1} ∗ such that x /∈ L.) 3. Given a formal system F , recall that Con (F ) is a mathematical encoding of the claim that F is consistent: in other words, that F never proves both that a statement is true and that it’s false. Consider the “self-hating sy stem” F +� Con(F ): that is, F plus the assertion of its own inconsistency. Show that if F is consistent, then F +� Con (F ) is an example of a formal system that is consistent but not so und. [Note: You can assume the Incompleteness Theorem.] 4. Let a XOR-circuit of size n be a circuit built entirely out of two-input XOR gates, which maps n input bits to n output bits. Also, call two circuits equivalent if they produce the same output whenever they’re g iven the same input. (a) Show that, for every XOR-circuit of size n, there’s an equivalent XOR-circuit with at most n (n − 1) gates. (b) Show that for every n, there’s some XOR-circuit of size n such that every eq uivalent XOR-circuit has Ω n2/ log n gates. 5. Suppo se a Turing machine M has s internal states, and visits at most n different tape squares. Prove an upper bound (in terms of n and s) on the number of steps until M halts (assuming it doe s