Typeset your answers neatly and submit a hardcopy solution at the beginning of class on 2012-02-21. You should consider using LaTeX, but I will not force you to do so.

Please note that many of these questions are not answerable solely from the course notes and textbooks. You may actually need to do some research—the web is fine. Remember to cite your sources. Also note that just because you pull data from a reputable source doesn't mean your answer will be good enough for full credit, let alone correct. Make sure your response answers the question, and answers it thoroughly. But be brief!

1. What is the significance of a set that is recursively enumerable but not recursive?
2. Characterize the sequence of integers (from GEB) 1 3 7 12 18 26 35 45 56 69.... How are the notions of figure and ground intertwined here?
3. Give formal systems for
   1. (Non-negative) Binary numerals divisible by 4
   2. (Non-negative) Binary numerals not divisible by 4
4. How is Hofstadter's Contracrostipunctus an acrostic? How is it self-referential?
5. How did the Tortoise show, in Contracrostipunctus, that there is no such thing as a "perfect record player"? How is this related to Gödel's demonstration that there is no "perfect" formal system for number theory?
6. What is meant by the statement that consistency is not an inherent property of a formal system?
7. In Hofstadter's Little Harmonic Labyrinth, is GOD a djinn? Why or why not?
8. Why was Achilles able to get a meta-wish, despite having his request for one passed sequentially through an infinite chain of genies?
9. Why did Achilles' wish ("I wish my wish would not be granted") in Little Harmonic Labyrinth cause an indescribable event to occur?
10. How does the discussion about "tonic" in Little Harmonic Labyrinth relate to the dialogue itself?