Godel, Escher, Bach Typographical Number Theory (TNT) puzzles and solutions

Question

In chapter 8 of Godel, Escher, Bach by Douglas Hofstader, the reader is challenged to translate these 2 statements into TNT:

"b is a power of 2"

and

"b is a power of 10"

Are following answers correct?:

(Assuming '∃' to mean 'there exists a number'):

∃x:(x.x = b)

i.e. "there exists a number 'x' such that x multiplied x equals b"

If that is correct, then the next one is equally trivial:

∃x:(x.x.x.x.x.x.x.x.x.x = b)

I'm confused because the author indicates that they are tricky and that the second one should take hours to solve; I must have missed something obvious here, but I can't see it!

Answer 1

Your expressions are equivalent to the statements "b is a square number" and "b is the 10th power of a number" respectively. Converting "power of" statements into TNT is considerably trickier.

Answer 2

In general, I would say "b is a power of 2" is equivalent to "every divisor of b except 1 is a multiple of 2". That is:

∀x((∃y(y*x=b & ¬(x=S0))) → ∃z(SS0*z=x))

EDIT: This doesnt work for 10 (thanks for the comments). But at least it works for all primes. Sorry. I think you have to use some sort of encoding sequences after all. I suggest "Gödel's Incompleteness Theorems" by Raymond Smullyan, if you want a detailed and more general approach to this.

Or you can encode Sequences of Numbers using the Chinese Remainder Theorem, and then encode recursive definitions, such that you can define Exponentiation. In fact, that is basically how you can prove that Peano Arithmetic is turing complete.

Try this:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

Then

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

should state "b is Power of 10", actually saying "there is a number y and a number k such that y is product of distinct primes, and the sequence encoded by k throug these primes begins with 1, has the property that the following element c of a is 10*a, and ends with b"

Answer 3

I think that most of the above have only shown that b must be a multiple of 4. How about this: ∃b:∀c:<<∀e:(c∙e) = b & ~∃c':∃c'':(ssc'∙ssc'') = c> → c = 2>

I don't think the formatting is perfect, but it reads:

There exists b, such that for all c, if c is a factor of b and c is prime, then c equal 2.

Answer 4

There's a solution to the "b is a power of 10" problem behind the spoiler button in skeptical scientist's post here. It depends on the chinese remainder theorem from number theory, and the existence of arbitrarily-long arithmetic sequences of primes. As Hofstadter indicated, it's not easy to come up with, even if you know the appropriate theorems.