I’ve recently started reading “Gödel, Escher, Bach: an Eternal Golden Braid” by Douglas R. Hofstadter, often abbreviated to GEB (ISBN-10: 9780465026562), and I’ve fallen completely in love with it. The combination of mind-warping arguments about math and logic, and Mr. Hofstadter’s ability to write in a way that scratches a very specific itch in my brain, make the experience of reading this book a rare joy for me.
But besides that, the book also contains a number of puzzles — in fact, it sometimes feels as if the entire book were a puzzle in and of itself — and so, for the first time in a long time (maybe ever?), I have felt compelled to add to my reading equipment a notebook and a pen.
So that’s what this is. A second year computer scientist’s (aggressively polished up) notes on GEB. Enjoy!
Note
It is very possible — and indeed probable — that this page contains a number of mathematical mistakes on my part. So everything on it should only be accepted after intense scrutiny on the reader’s part.
And if the reader were to find a specific mistake, please do let me know! I’d love nothing more than to revise some of these puzzles. I have loved doing them the first time as well, after all.
The MU-Puzzle (p. 35)
Process
Starting the puzzle, I’m quite sure that I’ll be able to solve it in a flash. We just discussed a system called “natural deduction” in uni, which I could probably just throw at this puzzle and hope it falls over.
So let’s bring the rules given in the book into the form we learned in uni:
- Alphabet: $\{\text{M},\text{I},\text{U}\}$
- Meta-Variables: $\{x,y\}$
- Inference rules: $$ \begin{gather*} \begin{prooftree} \AxiomC{} \RightLabel{MI} \UnaryInfC{$\Gamma\vdash\text{MI}$} \end{prooftree} \\[1em] \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{I}$} \RightLabel{R1} \UnaryInfC{$\Gamma\vdash x\text{IU}$} \end{prooftree} \qquad \begin{prooftree} \AxiomC{$\Gamma\vdash \text{M}x$} \RightLabel{R2} \UnaryInfC{$\Gamma\vdash \text{M}xx$} \end{prooftree} \\[1em] \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{III}y$} \RightLabel{R3} \UnaryInfC{$\Gamma\vdash x\text{U}y$} \end{prooftree} \qquad \begin{prooftree} \AxiomC{$\Gamma\vdash x\text{UU}y$} \RightLabel{R4} \UnaryInfC{$\Gamma\vdash xy$} \end{prooftree} \end{gather*} $$
- Prove: $\{\}\vdash\text{MU}$
and then set off trying to build a derivation tree.
[some trying and failing ensues]
Maybe I can simply use R2 over and over again, until I have a number of “I”’s that is divisible by three. Then I could simply add a “U” to the end of the string, turn the last three “I”’s into a “U”, remove the two resulting “U”’s and then simply rinse and repeat until I would be left with “MU”.
But wait … No power of two can be divisible by three … That follows from the uniqueness of the prime factorisation …
So not that then. Maybe the key is using R2 again after having removed the “I”’s, doubling the resulting number …
Oh man, this is more complicated than I’d imagined …
Wait! Maybe it’s just simply not possible?
[It follows a attempt at proving “MU” underivable in a system without R3 and then extrapolating that to the whole system. It fails.]
Hmm, okay, so R3 has to be the key in this somehow. Maybe we can get it by some repetition of: double the “I”’s using R2; remove 6 “I”’s using R3 and R4; repeat. So looking at the number of “I”’s, that would be a finite sequence of $({}\cdot 2);({}-6)$ operations. Is it even possible to get zero “I”’s from that?
We can try a modulo-test by looking at everything in modulo 3. We’d need:
$$ \begin{align*} &0 \stackrel{!}{\equiv}_3 ((((1 \cdot 2) - 6 ) \cdot 2 ) - 6 ) \dots \\ \dot\implies &0 \stackrel{!}{\equiv}_3 ((((1 \cdot 2) - 0 ) \cdot 2 ) - 0 ) \dots \end{align*} $$Ooooh waait, I think I see …
My Solution
The MU-puzzle is unsolvable, i.e. in the natural deduction system presented above, MU is not derivable.
Proof: Assume — towards a contradiction — that such a derivation is possible. Let us now examine the change in the number of “I”’s in a string that the application of each rule will produce:
- MI: The amount of “I”’s remains the same.
- R1: The amount of “I”’s remains the same.
- R2: The amount of “I”’s is doubled.
- R3: The amount of “I”’s is reduced by 3.
- R4: The amount of “I”’s remains the same.
Any derivation must start at “MI”, which contains exactly 1 “I”. And “MU” contains 0 “I”’s, so our derivation must start with 1 “I” and then, by some sequence of rule applications, arrive at 0 “I”’s. Hence, by the “I” manipulations presented above, we must be able to start at 1 and then, by some sequence of applications of $({}\cdot 2)$ and $({}-3)$, arrive at 0.
By $3\equiv_30$ and by modular arithmetic, we must therefore have:
$$ 0\stackrel{!}{\equiv}_31\cdot2\cdot2\cdot2\cdot2\cdots $$This is equivalent to saying that the right-hand term above must be divisible by three. But by the uniqueness of the prime factorisation, a power of two can never be divisible by three.
We’ve arrived at a contradiction, hence no such derivation can exist.
The Author’s Solution
Not yet stated where I am in the book …
Comments
As also stated by the author, it might be interesting to think about whether or not there is a decision procedure for the MU system, i.e. whether or not the language of derivable theorems of the MU systems is recursive.
Maybe we can somehow show that all strings which are not modulo-3-congruent to 0 are indeed derivable? Or maybe even directly how?
I’ll leave this one for the future, I think …
The tq-System (p. 47)
My Solution
A pq-string of the form:
$$ x\mathbf{p}y\mathbf{q}z $$is a theorem if and only if we can get back to $x\mathbf{p}-\mathbf{q}x-$ by removing exactly as many hyphens from $y$ (namely all but one) as we remove from $z$.
The Author’s Solution
A pq-string of the form:
$$ x\mathbf{p}y\mathbf{q}z $$if and only if the amount of hyphens in $x$ added to the amount of hyphens in $y$ adds up to the amount of hyphens in $z$.
Comments
Hah, duh! I actually managed to write down a description of addition (which I believe is actually also correct?) without noticing!
*imagine me facepalming here*