C o w a y M a c h i n e s --- F r a c t r a n ------------------------------------------------- From: Chris Landauer Date: Wed, 21 Aug 96 07:31:55 PDT Subject: Re: Conway Machines & Applications i am interested in seeing the proof that the prime machine works - i have seen one, and made one (long ago) more later, cal From: Bill Dubuque Date: Wed, 21 Aug 1996 13:28:49 -0400 Subject: Re: Conway Machines & Applications [was: short Godel sentences] Thanks for the pointer to your exposition. Here's further info: [1] Open problems in communication and computation. Edited by Thomas M. Cover and B. Gopinath. Springer-Verlag, New York-Berlin, 1987. viii+236 pp. ISBN: 0-387-96621-8 MR 89c:94003 (Reviewer: Wiktor Kulesza) 94-02 (68Q15 68Q25 68Q30 94A05 94A15) From: Bill Dubuque Date: Fri, 23 Aug 1996 18:12:10 -0400 Subject: Conway's PI Machine [was: Conway Machines & Applications [was: short Godel sentences]] John Conway wrote to math-fun on 8/21/96: : : ... The pi program is unfortunately bugged, although the bug : is a tiny one that I could correct in a few minutes when I saw it ... Here's your published PIGAME FRACTRAN program: 365 29 79 679 3159 83 473 638 434 89 17 79 46 161 575 451 413 407 371 355 335 235 209 122 31 41 517 111 305 23 73 61 37 19 89 41 833 53 183 115 89 83 79 73 71 67 61 59 57 53 47 43 86 13 23 67 71 83 475 59 41 1 1 1 1 89 41 38 37 31 29 19 17 13 291 7 11 1024 97 1 It computes pi(n), the nth digit of pi: 0 -> 3, 1 -> 1, 2 -> 4, ... i.e. when started on 2^n the next power of 2 to appear is 2^pi(n). -Bill From: Bill Dubuque Date: Tue, 27 Aug 1996 01:23:45 -0400 Subject: Re: Conway's PI Machine [was: Conway Machines & Applications [was: short Godel sentences]] I wrote: :Conway wrote: :> I haven't seen my copy of the Cover-Gopinath book for ages, or :>I could tell you my precise fix. I suppose I could just work it out :>again. : :If someone debugs the PI digits program I'll be happy to QA it by running :it through my FRACTRAN interpreter. I just noticed that the PI machine computes pi by employing over 4*2^10^n terms of Wallis' product, so clearly this program is infeasible for n > 1, i.e. its only a paper algorithm (unlike the PRIME enumeration program, which is slightly more feasible, e.g. it takes around a half-million operations to go from 97 to 101). Allan: the PI machine starts with input 2^n*89, not 2^n (this is a typo in Theorem 2 of Conway's paper); i.e. the machine is started in state 89 with r2=n, r3=r5=r7=r11=0. Note that primes < 13 are registers, others are states: if the accumulator = 2^m*...*11^n*q, q >= 13, then the machine is in state q with r2=m,...,r11=n). The algorithm proceeds in three phases: The first phase ends when state 37 is reached, with r2=0, r3=1, r5=E, r7=2*10^n, r11=0, where E >= 4*2^10^n and is even. The second phase ends when state 41 is reached, with r2 = r5 = r7 = 0, r3 = 10^n* 2*(E-0)*(E-2)*(E-2)*(E-4)*(E-4)*(E-6)*...*4*4*2*2 := N r11 = (E-1)*(E-1)*(E-3)*(E-3)*(E-5)*(E-5)*...*5*3*3*1 := D so that N/D = 10^n times the Wallis product for pi truncated at the term E/(E-1). The final phase computes the n'th digit by reducing the integer part of N/D mod 10. The term bound E = 4*2^10^n is justified via Mahler's irrationality measure for pi: | pi - p/q | > 1/q^42. I haven't checked any of these claims. Based on Conway's earlier remark I presume the bug is in the final phase. -Bill Date: Tue, 27 Aug 1996 10:44:54 -0400 (EDT) From: John Conway Subject: Re: Conway's PI Machine [was: Conway Machines & Applications [was: short Godel sentences]] On Tue, 27 Aug 1996, Bill Dubuque wrote: > > I wrote: > :Conway wrote: > :> I haven't seen my copy of the Cover-Gopinath book for ages, or > :>I could tell you my precise fix. I suppose I could just work it out > :>again. > : > :If someone debugs the PI digits program I'll be happy to QA it by running > :it through my FRACTRAN interpreter. > > I just noticed that the PI machine computes pi by employing over 4*2^10^n > terms of Wallis' product, so clearly this program is infeasible for n > 1, > i.e. its only a paper algorithm (unlike the PRIME enumeration program, > which is slightly more feasible, e.g. it takes around a half-million > operations to go from 97 to 101). > > Allan: the PI machine starts with input 2^n*89, not 2^n (this is a typo > in Theorem 2 of Conway's paper); i.e. the machine is started in state > 89 with r2=n, r3=r5=r7=r11=0. Note that primes < 13 are registers, others > are states: if the accumulator = 2^m*...*11^n*q, q >= 13, then the machine > is in state q with r2=m,...,r11=n). I'm worried about this 2^n.89 business : this is something I don't remember. Let me tell you that it's in the input and output phases that these things tended to become bugged. It's easy to write a program to pass from 89*2^n to 97*2^{f(n)} (say), but I always like to clean them up so that it goes from 2^n to 2^{f(n)}. Getting rid of the "97" is easy - you just add a terminal fraction 1/97, but getting rid of the "89" is a bit harder, because it tends to "merge" the input and output phases. My memory seems to be a bit shaky here, but my recollection is that I first worked this one out just to get a constant for the universal machine, and then converted it into a "stand-alone" program rather quickly, by doing one of these rub-outs, and hence the bug. I also tried hard to keep the numerators and denominators less than 1000, except for that 1024 which gave the natural way to reduce the answer modulo 10. This is the reason why I was perturbed by my quick fix, which changed 1024 to 7168, and why I always intended to go back and get a better one. John Conway > > The algorithm proceeds in three phases: > > The first phase ends when state 37 is reached, with > > r2=0, r3=1, r5=E, r7=2*10^n, r11=0, > > where E >= 4*2^10^n and is even. > > The second phase ends when state 41 is reached, with > > r2 = r5 = r7 = 0, > > r3 = 10^n* 2*(E-0)*(E-2)*(E-2)*(E-4)*(E-4)*(E-6)*...*4*4*2*2 := N > r11 = (E-1)*(E-1)*(E-3)*(E-3)*(E-5)*(E-5)*...*5*3*3*1 := D > > so that N/D = 10^n times the Wallis product for pi truncated at the > term E/(E-1). > > The final phase computes the n'th digit by reducing the integer > part of N/D mod 10. > > The term bound E = 4*2^10^n is justified via Mahler's irrationality > measure for pi: > > | pi - p/q | > 1/q^42. > > I haven't checked any of these claims. Based on Conway's earlier remark > I presume the bug is in the final phase. > > -Bill > I recalled that the bug was that after doing the computation it did something like deleting it. But, as I said, the input and output phases are effectively merged (both in the machine and my mind!), and it may well have been that it was that in the input phase it first reduced n modulo 10 (which is what it had to do in the output phase). Or that may be a new bug. This was actually a pretty easy program to write, because it was obvious that the 40 or so fractions I came up with weren't going to be reduced to about 20, so that there wasn't much point in "squeezing" it very hard. I worked VERY hard on squeezing the prime machine down, and REASONABLY hard on the universal one, but didn't bother at all with the PI one (apart from taking a little bit of care with the 1000 bound on numerators and denominators, which was almost automatic with me anyway) John Conway Date: Tue, 27 Aug 1996 16:27:24 -0400 (EDT) From: Allan Wechsler Subject: Fractran I announce my first Fractran program. It's very modest -- all it does is convert 2^n to 2^2n. 14/15 # A:=B and disarm 5/ 7 # re-arm 1/ 5 # Terminate 9/ 2 # B:=2*A 5/ 1 # arm Now I issue challenges: (1) Do the same thing with fewer fractions, or prove this impossible. (2) Do the same thing with fewer than four "registers", or prove this impossible. I confess that I don't exactly like the convention of putting the input into register 2 and reading the output from the same place. I'd like it better if the machine actually stopped, by falling off the end of the fraction chain. -A From: Bill Dubuque Date: Tue, 27 Aug 1996 18:24:00 -0400 Subject: Re: Conway's PI Machine [was: Conway Machines & Applications [was: short Godel sentences]] John Conway wrote to math-fun on 8/27/60: : :On Tue, 27 Aug 1996, Bill Dubuque wrote: :> ...Allan: the PI machine starts with input 2^n*89, not 2^n (this is a :> typo in Theorem 2 of Conway's paper); ... : : I'm worried about this 2^n.89 business : this is something I don't :remember. : : Let me tell you that it's in the input and output phases that these :things tended to become bugged. It's easy to write a program to :pass from 89*2^n to 97*2^{f(n)} (say), Yes, the proof of correctness for your PI machine that you sketch in section 9 does indeed employ a machine using 89*2^n -> 97*2^f(n), except you rename 97 -> 1 using the optimization mentioned on p. 16. : but I always like to clean them up so that it goes from : 2^n to 2^{f(n)}. Getting rid of the "97" is :easy - you just add a terminal fraction 1/97, but getting rid of the :"89" is a bit harder, because it tends to "merge" the input and output :phases. Yes, in Theorem 2 you append to the machine in section 9 the two final fractions 1/97, 89/1. It appears that the problem may be with the placement of 89/1: as Allan mentioned, this will fail to start the machine correctly in state 89 for any input >= 10 due to the 3rd-last fraction being 1/2^10. I haven't had any spare time to carefully check the proof, but I think others should now be able to since I've specified enough info to allow reconstruction of the state diagram; this, combined with the sketch of in my prior message of the operation of the three phases, should allow one to understand the machine with a little effort. -Bill Date: Wed, 21 Aug 1996 19:18:15 -0400 (EDT) From: John Conway Subject: Re: Conway Machines & Applications On Wed, 21 Aug 1996, Chris Landauer wrote: > > i am interested in seeing the proof that the prime machine works - > i have seen one, and made one (long ago) > > more later, > cal OK, here goes. The 14 fractions are 17 78 19 23 29 77 95 77 1 11 13 15 15 55 -- -- -- -- -- -- -- -- -- -- -- -- -- -- and are called 91 85 51 38 33 29 23 19 17 13 11 14 2 1 A B C D E F G H I J K L M N For fun I'll do most of the proof without words: 5^n.7^d.13 c: AB = 2x3/5x7 (AB)^n.J 2^d.3^n.5^(n-d).11 c: EF = 7/3 (EF)^n.K 2^d.5^(n-d).7^d.13 (AB)^n.J 2^2d.3^n.5^(n-2d).11 (EF)^n.K 2^2d.5^(n-2d).7^d.13 ........ 2^qd.5^r.7^d.13 c: n = qd+r , 0 =0) I(r=0) 2^n.3^(r-1).7^(d-r-1).19 2^n.7^(d-1) c: display! (DG)^n.H c: DG = 5/2 (L or M)^n.N 3^(r-1).5^n.7^(d-r).11 3^n.5^(n+1).11 (EF)^(r-1).K (EF)^n.K 5^n.7^(d-1).13 5^(n+1).7^d.13 So if you start from 5^n.7^(n-1).13 it will test each number in turn from n-1 down to 1 until it finds a divisor d of n, and then display 2^n.7^(d-1) before increasing n by 1. The displayed number will be a power of 2 if and only if n is prime. Tell me if you can follow this! John Conway Date: Wed, 21 Aug 1996 09:49:47 -0400 (EDT) From: John Conway Subject: Re: Conway Machines & Applications [was: short Godel sentences] On Tue, 20 Aug 1996, Bill Dubuque wrote: > John Conway wrote to math-fun on 8/17/96: > : > :I have a universal machine that's just a list of 21 fractions, say > :a,b,c,...,u. The step of the program is to multiply a given integer N > :by the first one of a,b,c,...,u that gives an integral answer ... > > A beautiful exposition of Conway machines may be found in Guy's article > "Conway's prime producing machine" ... I agree, but think my own exposition is even more beautiful! It gives not only my 14 fraction prime-producer, but a 38 fraction program for computing decimal digits of pi and a 21 fraction universal program. It's in "Problems in Communication", edited by T. Cover and B. Gopinath, along with my discussion of the sequence 1,11,21,1211,... . The pi program is unfortunately bugged, although the bug is a tiny one that I could correct in a few minutes when I saw it, but the others are OK as is, and the constant that makes the universal one compute digits of pi manages to escape the bug (which is in "the output", rather than the actual computation of digits of pi). Once again, I haven't a copy (and would appreciate it if anyone who finds copies of any of these things could send me some). However, I have a proof (much shorter than Guy's) that the prime machine works, which I'll happily put out here if anyone's interested. John Conway From: Bill Dubuque Date: Tue, 20 Aug 1996 20:26:04 -0400 Subject: Conway Machines & Applications [was: short Godel sentences] John Conway wrote to math-fun on 8/17/96: : :I have a universal machine that's just a list of 21 fractions, say :a,b,c,...,u. The step of the program is to multiply a given integer N :by the first one of a,b,c,...,u that gives an integral answer ... A beautiful exposition of Conway machines may be found in Guy's article "Conway's prime producing machine" -- see the MR below. Recall that I mentioned this article earlier on math-fun when I was discussing Conway's use of such machines in his proof of the undecidability of a certain class of congruential iteration problems similar to that of the Collatz 3x+1 problem and Burckel's generalizations (and how such problems surprisingly arose in the search for Busy Beaver machines). I've also appended below an MR which describes another application of Conway's "Unpredictable Iterations" paper to prove an analog in declarative (logic) programming of the famous Bohm-Jacopini result that one single while-do is enough for all programming (Comm. ACM 9 (1966), 366 - 371; Zbl 145, 242), a result often cited as justification for structured programming. Does anyone have access to the 1972 Boulder Number Theory Conf. Proc's in which Conway's "Unpredictable Iterations" paper appeared? If so, I would be most indebted if someone could send me a copy of this paper (Conway said he no longer has a copy). -Bill ------------------------------------------------------------------------------ 84j:10008 10A25 03D10 10-04 68C99 Guy, Richard K. Conway's prime producing machine. (English) Math. Mag. 56 (1983), no. 1, 26--33. ------------------------------------------------------------------------------ This elementary, beautifully written article describes Conway's prime producing machine, which is simply a specific ordered set of fourteen rational numbers r{sub}1, r{sub}2, ... ,r{sub}(14). A step in the execution of Conway's machine consists of multiplying the "current number" by the first r{sub}i in the sequence which produces a whole number answer. When the current number is a pure power of two, i.e. 2{sup}p, then p is output as the next prime. If the machine is started with current number 2=2{sup}1, nineteen steps produce 4=2{sup}2, fifty more produce 2{sup}3 and 211 more give 2{sup}5. The author shows that Conway's machine really consists of four registers, can be in one of fourteen different states and can only add one to a register, subtract one from a register or test if a register is zero. He then simplifies the Conway program by introducing a collection of subroutines or "macros" which are aggregates of simple instructions. Using these, the author shows that the Conway program is equivalent to a well-known (although highly inefficient) procedure for inspecting the next number for primality. His running analysis shows that inspecting the thousandth prime (8831) would require 468 056 052 atomic steps. Reviewed by M. C. Wunderlich ------------------------------------------------------------------------------ 95j:68050 68Q05 03B70 Devienne, Philippe (F-LILL-FI); Lebegue, Patrick (F-LILL-FI); Routier, Jean-Christophe (F-LILL-FI); Wurtz, Jorg One binary Horn clause is enough. (English. English summary) STACS 94 (Caen, 1994), 21--32, Lecture Notes in Comput. Sci., 775, Springer, Berlin, 1994. ------------------------------------------------------------------------------ Summary: "This paper proposes an equivalent form of the famous Bohm-Jacopini theorem for declarative languages. C. Bohm and G. Jacopini [Comm. ACM 9 (1966), 366--371; Zbl 145, 242] proved that all programming can be done with at most one single while-do. That result is cited as a mathematical justification for structured programming. A similar result can be shown for declarative programming. Indeed, the simplest class of recursive programs in Horn clause languages can be defined by the following scheme: $\scr A\sb 1\leftarrow, \scr A\sb 2\leftarrow\scr A\sb 3, \leftarrow\scr A\sb 4$; that is, $$\forall x\sb 1\cdots\forall x\sb m[\scr A\sb 1\wedge(\scr A\sb 2\vee\254\scr A\sb 3)\wedge\254\scr A\sb 4],$$ where the $\scr A\sb i$ are positive first-order literals. This class is shown here to be as expressive as Turing machines and all simpler classes would be trivial. The proof is based on a remarkable and insufficiently known codification of any computable function by unpredictable iterations proposed by J. H. Conway [in Proceedings of the Number Theory Conference (Boulder, CO, 1972), 49--52, Univ. Colorado, Boulder, CO, 1972; MR 52 #13717]. Then, we prove effectively by logical transformations that all conjunctive formulas of Horn clauses can be translated into an equivalent conjunctive 4-formula (as above). Some consequences are presented in several contexts (mathematical logic, unification modulo a set of axioms, compilation techniques and other program patterns)."