Remember that it's legitimate to talk about a set of numbers, a set of pairs of numbers, a set of functions, etc., and that the member of a member of a set is not automatically a member of the set itself. (So Bill Clinton is a member of the set Mr. and Mrs. Clinton, but he is not a member of the set All Married Couples.) $\mathbf{N} = \{0,1,2,3,...\}$ denotes the set of natural numbers. Recall that an infinite set $S$ is countable iff there exists a bijection pairing up all members of $S$ with members of $\mathbf{N}$.

1. Just give short answers for these.
   1. Here's the beginning of an infinite bitstring (all omitted trailing bits are 0s): 1010100.... What (specifically) does this string mean/refer to if you interpret is as the characteristic function defining a subset of the natural numbers?
   2. What (specifically) does it mean/refer to if you interpret it as the portion of a binary number to the right of the "decimal" point (assume there's nothing to the left of it but 0s)?
   3. How many different possible bitstrings are there of length 5?
   4. How many different possible subsets are there of the set $\{0,1,2,3,4\}$? (Remember that the empty set and the set itself both count as (trivial) subsets.)
   5. How many different possible functions can be defined from the set $\{0,1,2,3,4\}$ to the set $\{0,1\}$. (Not just bijections, all functions.)

2. The following three sets are all clearly infinite. For each one, say whether it is countable or uncountable, and give brief explanations.
   1. Let $S$ be the set of all finite-length sequences of natural numbers. (Recall the sequence numbers $< a_1,a_2,...,a_n >$.)
   2. Let $P$ be the set of all possible Python programs.
   3. Let $F$ be the set of all possible mathematical functions from $\mathbf{N}$ to $\{0,1\}$.
   4. Briefly explain why it follows that some members of $F$ must be uncomputable functions, i.e., functions for which there is no possible Python program that computes them.

3. Goldbach's Conjecture states that every even number greater than 2 can be written as the sum of two primes, but there is no known proof of this.

   Suppose the halting problem was decidable, i.e., there exists an algorithm/Turing machine $H$ that, for any program $M$ and input $x$, will tell you whether $M$ running on $x$ eventually halts or not. (Of course it also responds correctly if you ask it about any program $M$ running on an empty input.)

   Explain how (i.e., describe a simple algorithm), using $H$, you could determine whether the Conjecture is true or false.

4. Suppose you have two Turing Machines $M_1$ and $M_2$: when run (on empty input), one of them eventually halts and prints the meaning of life, and the other just runs forever. Unfortunately, you don't know which is which.

   Suppose you have a slightly fancier UTM than the one described in class. Your UTM $U$ takes a machine $M$, an optional input $x$ (not needed here), and a bound on the running time $n$: it simulates $M$, but only for up to $n$ steps (i.e., applications of its $\delta(\cdot,\cdot)$ function). If $M$ halts within $\le n$ steps, then $U(M,n)$ completes the simulation in the normal way, but if $M$ hasn't halted by that point, $U(M,n)$ prints "OUT OF TIME" and halts.

   1. Using $M_1,M_2$, and $U$, describe a simple algorithm you could use to determine the meaning of life. To count as a valid algorithm, it must be always guaranteed to eventually halt and print out the meaning of life.
   2. Suppose the machine printing the meaning of life does so after some number $t$ time steps (of course you don't know what $t$ is), and let $f(t)$ be the total time your algorithm takes to finish finding the meaning of life, in the worst case, as a function of $t$. What is $f(t)$? (Roughly, in the big-O sense.)
   3. Can you find an algorithm whose running time is linear in $t$, i.e., so that $f(t) \le k\cdot t$ for some fixed value $k$ (like, say, 2 or 4 or 200)?