Blog by Sumana Harihareswara, Changeset founder
I'm still reading Douglas Hofstadter's G�del, Escher, Bach, and I'm…
Hi, reader. I wrote this in 2002 and it's now more than five years old. So it may be very out of date; the world, and I, have changed a lot since I wrote it! I'm keeping this up for historical archive purposes, but the me of today may 100% disagree with what I said then. I rarely edit posts after publishing them, but if I do, I usually leave a note in italics to mark the edit and the reason. If this post is particularly offensive or breaches someone's privacy, please contact me.
I'm still reading Douglas Hofstadter's G�del, Escher, Bach, and I'm in the chapter entitled Typographical Number Theory. (By the way, even though I've seen Hofstadter in person and in pictures, whenever I try to picture him I get this vision of Nathaniel Smith. Bright, cocky, and enviable, that sort of thing.)
Around the middle of the chapter, Hofstadter throws out a few exercises-for-the-reader in translation from English to Typographical Number Theory (in which only the natural numbers exist). He doesn't provide the answers anywhere that I can see, but Leonard agreed with my answers for the first four puzzles, so I thought I was ready for the fifth:
b is a power of 2.
Leonard didn't know how to translate it (that darn inability to represent recursion!), and thought it might have to do with something called the Chinese Remainder Theorem, but sort of gave up and went back to rereading The Lord of the Rings. I kept plugging away, trying to solve it, since I knew that a solution existed.
I tried an approach that reasoned, "b is either equal to 1, or it's a product of 2 and a, where a is some power of 2." But that leads to recursion and I don't know how to represent recursion in TNT.
Then I tried to think about the properties of powers of 2. And powers of 2 are never odd (except for 1), and powers of 2 are not divisible by any odd numbers (except for 1). The first rule there is realy a sub-rule of the second, so:
b is not the product of any odd number (except one) and any other number.
I don't know how to represent the various typographical notations in HTML, but here's a translation of my TNT representation of the above logic:
For all a, For all c, a equals zero, or b does not equal (c times (one plus (two times a)))
Am I right? Or am I missing something? I think I am missing something. Probably there's some insidious loophole involving the possibility that c is odd or something. What is the "right" translation?
(By the way, Hofstadter merely describes this problem with: "may be a little tricky.")
(I get the sense that Seth's diary will feel this entry call out to it, deep calling to deep, and put up an answer to my question without Seth even having to write it.)
