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

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.

Answer 4

how about:

∀x: ∀y: (SSx∙y = b → ∃z: z∙SS0 = SSx)

(in English: any factor of b that is ≥ 2 must itself be divisible by 2; literally: for all natural numbers x and y, if (2+x) * y = b then this implies that there's a natural number z such that z * 2 = (2+x). )

I'm not 100% sure that this is allowed in the syntax of TNT and propositional calculus, it's been a while since I've perused GEB.

(edit: for the b = 2ⁿ problem at least; I can see why the 10ⁿ would be more difficult as 10 is not prime. But 11ⁿ would be the same thing except replacing the one term "SS0" with "SSSSSSSSSSS0".)

Answer 5

In expressing "b is a power of 10", you actually do not need the Chinese Remainder Theorem and/nor coding of finite sequences. You can alternatively work as follows (we use the usual symbols as |, >, c-d, as shortcuts for formulas/terms with obvious meaning):

1. For a prime number p, let us denote EXP(p,a) some formula in TNT saying that "p is a prime and a is a power of p". We already know, how to build one. (For technical reasons, we do not consider S0 to be a power of p, so ~EXP(p,S0).)

2. If p is a prime, we define EXP_p(c,a) ≖ ⟨EXP(p,a) ∧ (c-1)|(a-1)⟩. Here, the symbol | is a shortcut for "divides" which can be easily defined in TNT using one existencial quantifier and multiplication; the same holds for c-1 (a-1, resp.) which means "the d such that Sd=c" (Sd=a, resp.).
   If EXP(p,c) holds (i.e. c is a power of p), the formula EXP_p(c,a) says that "a is a power of c" since a ≡ 1 (mod c-1) then.

3. Having a property P of numbers (i.e. nonnegative integers), there is a way how to refer, in TNT, to the smallest number with this property: ⟨P(a) ∧ ∀c:⟨a>c → ~P(a)⟩⟩.

4. We can state the formula expressing "b is a power of 10" (for better readability, we omit the symbols ⟨ and ⟩, and we write 2 and 5 instead of SS0 and SSSSS0):
   ∃a:∃c:∃d: (EXP(2,a) ∧ EXP(5,c) ∧ EXP(5,d) ∧ d > b ∧ a⋅c=b ∧ ∀e:(e>5 ∧ e|c ∧ EXP₅(e,c) → ~EXP₅(e,d)) ∧ ∀e:("e is the smallest such that EXP₅(c,e) ∧ EXP₅(d,e)" → (d-2)|(e-a))).

Explanation: We write b = a⋅c = 2^x⋅5^y (x,y>0) and choose d=5^z>b in such a way that z and y are coprime (e.g. z may be a prime). Then "the smallest e..." is equal to (5^z)^y = d^y ≡ 2^y (mod d-2), and (d-2)|(e-a) implies a = 2^x = e mod (d-2) = 2^y (we have 'd-2 > 2^y' and 'd-2 > a', too), and so x = y.

Remark: This approach can be easily adapted to define "b is a power of n" for any number n with a fixed decomposition a₁a₂...a_k, where each a_i is a power of a prime p_i and p_i = p_j → i=j.

Answer 6

Here's what I came up with:

∀c:∃d:<(c*d=b)→<(c=SO)v∃e:(d=e*SSO)>>

Which translates to:

For all numbers c, there exists a number d, such that if c times d equals b then either c is 1 or there exists a number e such that d equals e times 2.

Or

For all numbers c, there exists a number d, such that if b is a factor of c and d then either c is 1 or d is a factor of 2

Or

If the product of two numbers is b then one of them is 1 or one of them is divisible by 2

Or

All divisors of b are either 1 or are divisible by 2

Or

b is a power of 2

Answer 7

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 8

Here is what I came up with for the statement "b is a power of 2"

∃b: ∀a: ~∃c: ((a * ss0) + sss0) * c = b

I think this says "There exists a number b, such that for all numbers a, there does not exist a number c such that (a * 2) + 3 (in other words, an odd number greater than 2) multiplied by c, gives you b." So, if b exists, and can't be zero, and it has no odd divisors greater than 2, then wouldn't b necessarily be 1, 2, or another power of 2?

Answer 9

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 10

my solution for b is a power of two is : ∀x: ∃y x.y=b ( isprime(x) => x = SS0 )

isprime() should not be hard to write.