-
Groucho Marx said he wouldn't join any club that would have him as a member. Define the club $G$ as the club for people like Groucho, i.e., that accepts people iff they won't join. Prove by diagonalization that no such club can exist. (Be clear about what the rows, columns, and cells in your table represent.)
-
Prove by diagonalization that the set of all decimal numbers between 0 and 1--or equivalently, the set decimal representations of these numbers--is uncountable. In your proof, each cell of the table should have a digit (0..9) rather than a bit.
One complication with base-10 is that there are multiple representations of the same number, e.g. 0.5 and 0.499999... Why does this pose an issue for the construction of your antidiagonal number?
-
Recall the structure of the diagonalization argument for proving $|P(N)|>|N|$: take any enumeration of the subsets $S_0,S_1,S_2,...$ of $N$ (i.e., mapping from $N$ to $P(N)$), draw the table where row $i$ corresponds to set $S_i$, column $i$ corresponds to number $i$, and in cell (i,j) is a bit $b_{ij}$ equaling 1 if $j \in S_i$ and 0 otherwise. Then define the antidiagonal $\overline D$, argue that 1) $\overline D$ ought to be one of the rows of the table, and 2) it doesn't. Therefore the enumeration was incomplete.
Why can't you apply the same argument to, say, $S=\{0,1,2,3\}$? and $P(S)$? Of course $|P(S)|>|S|$, but does the argument succeed in successfully "proving" that every enumeration of $P(S)$ is incomplete? Where does it fail?
-
Recall the following definitions:
- $\phi_D(x) = x(x)$
- $\phi_{\overline D}(x) = \text{not provable}(x(x))$
- $\gamma = \phi_{\overline D}(\overline D) = \text{not provable}(\phi_{\overline D}(\overline D))$, which we can interpret as saying, "I am not provable."
Now consider the following wffs with no free variables (i.e., statements):
- $\phi_{\overline D}(\overline D)$
- $\phi_D(D)$
- $\phi_D(\overline D)$
- $\phi_{\overline D}(D)$
Which of these (if any) are equivalent? What does each of them "say"? For each, state whether it is true/false/unknown and whether it is provable/not provable/unknown.
-
For a Turing Machine $M$, let $L(M)$ indicate the set of all inputs $x$ on which $M$ halts.
Let SAMELANG = $\{\text{TMs } (M_1,M_2): L(M_1)=L(M_2)\}$. Show that SAMELANG is undecidable, by reduction from EMPTY ($\{\text{TM } M: L(M) = \emptyset\}$), i.e., show that if you had some algorithm for deciding SAMELANG, then you would also be able to decide EMPTY. ("Decide" a language $L$ means having an algorithm/TM that, for any $x$, correctly determines whether or not $x \in L$. Oh, and here a "language" is just some particular set of strings, in this case a set of bitstrings.)
-
Let $BB(n)$ be the maximum number of steps that any TM with $n$ states runs before halting (on the empty input), i.e. among all the different possible TMs with $n$ states, the maximum number $b$ such that there's one of these $n$-state TMs that runs for $b$ steps (on empty input), and then halts.
Prove that $BB(n)$ is uncomputable, by reduction from HALTING, i.e., show that if $BB(n)$ were computable then HALTING would be decidable. ("Computable" means there exists an algorithm/TM that, for any input $n$, will print out $BB(n)$ and halt.)