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)."