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

For the open expression meaning that b is a power of 2, I have ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

This effectively says that for all a, S(Sa ∙ SS0) is not a factor of b. But in normal terms, S(Sa ∙ SS0) is 1 + ((a + 1) * 2) or 3 + 2a. We can now reword the statement as "no odd number that is at least 3 is a factor of b". This is true if and only if b is a power of 2.

I'm still working on the b is a power of 10 problem.

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

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.