postpischil@being.DEC (Always mount a scratch monkey.) (01/02/86)
I don't think this got posted the first time I tried it, so I am trying again. In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b is a power of 10" in Typographical Number Theory. Does anybody have a solution for this? -- edp Eric Postpischil "Always mount a scratch monkey."
verma@ucla-cs.UUCP (01/19/86)
--------------- This line intentionally left blank --------------- In article <226@decwrl.DEC.COM>, Eric asks: >I don't think this got posted the first time I tried it, so I am trying again. > >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >is a power of 10" in Typographical Number Theory. Does anybody have a solution >for this? He asked this January second; it is now the EIGHTEENTH! That is SIXTEEN days to get the answer. This is net.math is it not? I have only one more question, Why is it that when simple questions are asked on this net there seem to be nearly a thousand 'GENIUSES', each giving his/her own version of the answer, but whenever any resonable problem is asked, it is promptly ignored?
bs@faron.UUCP (Robert D. Silverman) (01/20/86)
> --------------- This line intentionally left blank --------------- > > In article <226@decwrl.DEC.COM>, Eric asks: > > >I don't think this got posted the first time I tried it, so I am trying again. > > > >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b > >is a power of 10" in Typographical Number Theory. Does anybody have a solution > >for this? > > He asked this January second; it is now the EIGHTEENTH! That is SIXTEEN days > to get the answer. This is net.math is it not? I have only one more question, > > Why is it that when simple questions are asked > on this net there seem to be nearly a thousand > 'GENIUSES', each giving his/her own version of > the answer, but whenever any resonable problem > is asked, it is promptly ignored? Sarcasm aside, I can suggest several reasons: 1. While I read GEB I found it overly simplistic and didn't bother with some of the details such as all the syntactic nuances of typographical number theory. I'm not aware of it appearing elsewhere. As such, problems involving it would have limited scope and interest. Maybe people don't find it an interesting or important problem. I know that I didn't. 2. What makes YOUR assertion that this is a resonable (sic) problem definitive? People have many things to do other than answer problems which derive from some single source and have limited use outside of its own context. 3. Sometimes problems which are simple to state have very complicated solutions (e.g. 4 color problem etc. etc. etc.) It may not be a simple problem to solve. I can't realy say since I haven't looked at it. I did find your comments extremely offensive however. 4. By the way I notice that YOU failed to post a solution. Bob Silverman
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (01/20/86)
>>In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >>is a power of 10" in Typographical Number Theory. Does anybody have a solution >>for this? > >He asked this January second; it is now the EIGHTEENTH! That is SIXTEEN days >to get the answer. This is net.math is it not? I have only one more question, > > Why is it that when simple questions are asked > on this net there seem to be nearly a thousand > 'GENIUSES', each giving his/her own version of > the answer, but whenever any resonable problem > is asked, it is promptly ignored? I couldn't imagine duller problems than DHs. In fact, I can't imagine anyone publically admitting they ever read GEB! ucbvax!brahms!weemba Matthew P Wiener UCB Math Dept Berkeley CA 94720
wdm@ecn-pc.UUCP (Tex) (01/22/86)
In article <8431@ucla-cs.ARPA> verma@ucla-cs.UUCP writes: > > Why is it that when simple questions are asked > on this net there seem to be nearly a thousand > 'GENIUSES', each giving his/her own version of > the answer, but whenever any resonable problem > is asked, it is promptly ignored? Don't answer that. Conspiracy forever, Bill Michael
gwyn@brl-tgr.UUCP (01/22/86)
> >I don't think this got posted the first time I tried it, so I am trying again. > > > >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b > >is a power of 10" in Typographical Number Theory. Does anybody have a solution > >for this? > > He asked this January second; it is now the EIGHTEENTH! That is SIXTEEN days > to get the answer. This is net.math is it not? I have only one more question, > > Why is it that when simple questions are asked > on this net there seem to be nearly a thousand > 'GENIUSES', each giving his/her own version of > the answer, but whenever any resonable problem > is asked, it is promptly ignored? Probably because nobody really cares about TNT. Certainly those who do have better things to do than to tediously express "b is a power of 10" in it.
franka@mmintl.UUCP (Frank Adams) (01/23/86)
In article <8431@ucla-cs.ARPA> verma@ucla-cs.UUCP writes: >In article <226@decwrl.DEC.COM>, Eric asks: > >>I don't think this got posted the first time I tried it, so I am trying >>again. >> >>In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >>is a power of 10" in Typographical Number Theory. Does anybody have a >>solution for this? > >He asked this January second; it is now the EIGHTEENTH! That is SIXTEEN days >to get the answer. This is net.math is it not? I have only one more >question, > > Why is it that when simple questions are asked > on this net there seem to be nearly a thousand > 'GENIUSES', each giving his/her own version of > the answer, but whenever any resonable problem > is asked, it is promptly ignored? I think this criticism is off the mark. The reason he didn't get any answers is because nobody had any. I suspect that the answer is that there is no such representation; but a proof thereof is more suitable for a thesis than for a net article. Do you really want everybody who doesn't know the answer to reply? Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
msb@lsuc.UUCP (Mark Brader) (01/25/86)
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? Mark Brader, B.Math(C.S.), M.Math(C.S.) P.S. - Let's not have 52 followups saying "I agree with Brader" or "I agree with Wiener". This is the first posting of this kind on my machine. If you want to express simple agreement, use mail. Mail to whoever you agree with, and make us both happy.
weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) (02/02/86)
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 <a,b,c,...,u> 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<p and a<p**i. This is a correct assertion, but that p**i is stuck in there. We know how to recognize that p**i is some power of p, but not how to get the actual exponent. To overcome this obstacle, we use a fiendishly clever idea. Instead of counting 0,1,2,...,n,Sn,SSn,..., let's count 1,p,p**2,...,p**n, p**Sn,p**SSn,.... In effect, we are encoding the integers in the powers of p, and simulating the successor function via multiplication by p. We don't extract the j'th digit of x base p, but the p**j's place of x base p. This actually is how we talk (100's place), but to notice that is what we need is amazingly difficult! So let's define k=place(x,p,q) k is the q's place Eab(x=a+(k+p*b)*q and k<p and a<q) of x base p [if ppower(p,q)] [=0 if not] [if not ppower(p,q), place is not well-defined, so we crash instead] This gives us sequence coding but it does not yet give us how long they are. One more clever idea is needed. Given the one sequence, we run another one parallel, namely <0,1,2,...> 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<n. This was Godel's original way of coding sequences. Since no one I know of has published Kripke's method, I suspect this was the solution DH had in mind in his book. ucbvax!brahms!weemba Matthew P Wiener/UCB Math Dept/Berkeley CA 94720