This section is on undecidability, uncountability, and complexity.

(20 points) Uncountability / Diagonalization (a) At the Dawn of Time, an infinite sequence of Pennies from Heaven fell to Earth aligning themselves in alternating Halos and Tridents extending over the horizon to the Twelfth of Never. Raumoko, the Maori god of earthquakes plays "Quaboom" with these coins. He leaps and comes crashing back down to earth so as to cause the coins to bounce and flip and tumble randomly. The effect of his jumps, however, never reaches beyond the horizon. The outcome of a game can be thought of as an infinite sequence over {H, T} that eventually alternates (with H at odd indices and T at even indices, as below). Are there countably infinitely many or uncountably infinitely many such sequences for the game "Quaboom"? Explain/prove your answer. Some sample "games" of Quaboom: HTHTHTHTHTHTHTHT... THTHTHTHTHTHTHTH... HHHHHHHHHHHHHHHH.. TTTTTTTTTTTTTTTT.. TTTHTHTTTHTHTHTT.. HHHTTHTHTHTHHTHT... HTHTHTHTHTHTHTHT... HTHTHTHTHTHTHTHT... HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT... (b) The Divinic Code of a god is made up of a sequence of Supremo Acrids: Genetica, Theobroma, Cornucopia, and Ambrosia. Every such infinite sequence of these Supremo Acrids corresponds to a different god. Are there countably infinitely many gods or uncountably infinitely many? Explain/prove your answer. Sample Divinic Codes of some of the gods: Gaia: Zeus: Odin Thor: Shiva: Jobs: GGGGGGGGGGGGGGG... GGGGGGGGGGGGGGG... AGTCAGTCAGTC... TCAGTCAGTCAG... GTACTAGCACATGATCAGT... GATCAACCAATGACTAG... TTTTTTTTTTTTTTTT... TTTTTTTTTTTTTTTTTT... ATGCTAGCATGAC... GATTACAGATTACA... ATTGGGCCCCAAAAATTTTTTGGGGGGGCCCCCCCC... Hint 1: One of these is countably infinite, the other uncountably infinite. Hint 2: One of these is equivalent to the rational numbers Q, the other to the reals R. (5 points) Bonus The diagonalization argument FAILS in one of these. Why? (20 points) Uncountability / Diagonalization (a) At the Dawn of Time, an infinite sequence of Pennies from Heaven fell to Earth aligning themselves in alternating Halos and Tridents extending over the horizon to the Twelfth of Never. Raumoko, the Maori god of earthquakes plays "Quaboom" with these coins. He leaps and comes crashing back down to earth so as to cause the coins to bounce and flip and tumble randomly. The effect of his jumps, however, never reaches beyond the horizon. The outcome of a game can be thought of as an infinite sequence over {H, T} that eventually alternates (with H at odd indices and T at even indices, as below). Are there countably infinitely many or uncountably infinitely many such sequences for the game "Quaboom"? Explain/prove your answer. Some sample "games" of Quaboom: HTHTHTHTHTHTHTHT... THTHTHTHTHTHTHTH... HHHHHHHHHHHHHHHH.. TTTTTTTTTTTTTTTT.. TTTHTHTTTHTHTHTT.. HHHTTHTHTHTHHTHT... HTHTHTHTHTHTHTHT... HTHTHTHTHTHTHTHT... HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT. HTHTHTHTHTHTHTHT... (b) The Divinic Code of a god is made up of a sequence of Supremo Acrids: Genetica, Theobroma, Cornucopia, and Ambrosia. Every such infinite sequence of these Supremo Acrids corresponds to a different god. Are there countably infinitely many gods or uncountably infinitely many? Explain/prove your answer. Sample Divinic Codes of some of the gods: Gaia: Zeus: Odin Thor: Shiva: Jobs: GGGGGGGGGGGGGGG... GGGGGGGGGGGGGGG... AGTCAGTCAGTC... TCAGTCAGTCAG... GTACTAGCACATGATCAGT... GATCAACCAATGACTAG... TTTTTTTTTTTTTTTT... TTTTTTTTTTTTTTTTTT... ATGCTAGCATGAC... GATTACAGATTACA... ATTGGGCCCCAAAAATTTTTTGGGGGGGCCCCCCCC... Hint 1: One of these is countably infinite, the other uncountably infinite. Hint 2: One of these is equivalent to the rational numbers Q, the other to the reals R. (5 points) Bonus The diagonalization argument FAILS in one of these. Why