Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!ittatc!dcdwest!sdcsvax!ucbvax!brahms!weemba From: weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) Newsgroups: net.math Subject: Re: Godel, Escher, Bach problem Message-ID: <11684@ucbvax.BERKELEY.EDU> Date: Sun, 2-Feb-86 07:23:31 EST Article-I.D.: ucbvax.11684 Posted: Sun Feb 2 07:23:31 1986 Date-Received: Mon, 3-Feb-86 05:17:29 EST References: <8431@ucla-cs.ARPA> <11461@ucbvax.BERKELEY.EDU> <1065@lsuc.UUCP> Sender: usenet@ucbvax.BERKELEY.EDU Reply-To: weemba@brahms.UUCP (Matthew P. Wiener) Organization: University of California, Berkeley Lines: 138 Summary: at long last solved In article <1065@lsuc.UUCP> msb@lsuc.UUCP (Mark Brader) writes: >Somebody posted a problem from "Goedel, Escher, Bach" and somebody >else complained in this way that there were no responses: > >> > Why is it that ... whenever any resonable problem >> > is asked, it is promptly ignored? > >To this Matthew P. Wiener (weemba@brahms.UUCP) replied: > >> I couldn't imagine duller problems than DHs. In fact, I can't imagine >> anyone publically admitting they ever read GEB! > >I'm tempted to reply at flaming length, but will just say that I find >[DM]r. Wiener's taste as bad as his spelling. I have not only *read* GEB, >I consider it one of the most interesting books I have *ever* read. >Am I "anyone" enough for you, and is net.math public enough for you, >or do I have to mention the Pulitzer Prize committee too? My rudeness clearly requires publicly apologizing. As penance, I give one solution to (a slight generalization of) the original problem. As an even more painful form of penance, I admit that I have read GEB. The problem: How do you express a=b**c using only + * S 0 and logical symbols. [S is the successor function, A E will be used for quantifiers. '->' will be used for implies. I will use x_y to mean x sub y. By integer I mean any non-negative integer. PA stands for Peano arithmetic, which Hofstadter calls TNT. All sequences are zero based, ie, I count 0,1,2,....] The main hurdle, after which any similar problem (how do you express a=b!, etc. in PA) can be solved rather easily, is to find a way to express sequences. For example, a=b**c is defined inductively by letting s_0=1, s_1=b, ..., s_Si=b*s_i, ..., and finally letting a=s_c. Thus a=b**c is true iff there exists a sequence s of length c+1, whose first element is 1, whose Si'th element is b times its i'th element (for all i<=c), and whose last term is a. Now, PA and basic logic does not have sequences built into the language. Godel's brilliant idea was that PA could fake it instead using sequence codes and appropriate sequence extraction functions. A sequence code is just a single number that contains all the information that a sequence of several numbers has. Such information, namely the sequence values, is extracted using particular functions applied to the sequence codes. The simplest example is base 10 sequences. For example, the number 123 is a code for the sequence <1,2,3>. f_0(x):='leading digit of x' will extract the 0th term of the sequence. This has several defects. The most obvious is that only sequences with values at most 9 can be coded. That can be cured by going to higher base arithmetic. But the question of how to extract the j'th digit from a number n written in base k needs to be solved. So let's solve it! The method I present is due to Saul Kripke. We need to define some predicates, that is, expressions that are true or false based on their parameters. Predicate English Peano Arithmetic div(m,n) m divides n Ex(m*x=n) prime(p) p is prime Ax(div(m,p) -> (m=1 or m=p)) ppower(p,q) q is a power of p, prime(p) and Ax(div(x,q) -> div(x,p)) and p is a prime. We want to express a sequence as the number u...cba base p where p is a prime greater than all of a,b,c,...,u. But how do you extract the j'th digit (counting from right to left, zero based as usual)? The obvious try is k = j'th digit of x base p iff x = a + (k+p*b) * p**i and k

to do the *actual* counting! Define count(y,p, y is counting in 0=place(y,p,1) and Asj[(div(p*s,q) and r,q,k) base p, up to the j=place(y,p,s)) -> j+1=place(y,p,s)] q's place, and in and ppower(p,q) the r's place the value counted was k, where p**k=q. The original suggestion for defining a=b**c was as follows: E sequence s (s_0=1, Ai(i<=c -> s_Si=b*s_i), s_c+1=a). Our solution is to simulate sequences as follows: Ex,y,p,q,s(place(x,p,1)=1, Ar(div(r,q) -> place(x,p,p*r)=b*place(x,p,r)), count(y,p,s,q,c) and place(x,p,s)=a). We claim that a=b**c iff the above statement holds. Suppose a=b**c. Then consider the sequence <1,b,b**2,...,b**c>. Pick a prime number p larger than a. Let q be a power of p greater than p**c. Let x = 1+b*p+b**2*p**2+...+b**c*p**c = ((b*p)**(c+1) - 1)/(b*p - 1). Let y = p+2*p**2+...+c*p**c = (c*p**(c+2) - (c+1)*p**(c+1) + p)/(p - 1)**2. Let s = a. Then our values x,y,p,q,s satisfy the needed properties. Conversely, given x,y,p,q,s satisfying the above, we are forcing x to be a number, when written in base p, whose digits, up to the q's place, that are the powers of b. And the p**c's place is a, because of the counting effect of y. It really works! [I should point out is just a coincidence that our problem and our coding both involve exponentiation. If it seems to get in the way, try the method on a=b! instead. [Actually, I might have blown a few letters here and there. Do NOT post or e-mail corrections. The net and I thank you in advance.] One more point. Do you really want to see the above written out in gory detail? That should not be too hard using the C preprocessor! Exercise for the more mathematical among you. (Prerequisites: the Chinese Remainder Theorem) Define beta(x,y,i) := x % (1+(i+1)*y) [here a%b := a reduced mod b] [Godel] Show that for all sequences s of length n, there exist x,y such beta(x,y,i) = s_i for all i