[math-fun] Adam's pi machine
Some funsters might not recognize Adam as the the author of the spectacular Life configuration that computes pi in decimal (and even displays the digits). Maybe someday he can explain to us if and how he solved the ".999 problem", i.e., the absence of an a priori bound on the number of possible consecutive 9s or 0s, which, until they cease, leave the preceding digit unresolved (or equivalently, provoke negative or oversize "apology digits" following the premature estimate of an earlier one). The corresponding problem with continued fraction output is the unboundedness of a term. Both Neil's and my calculations simply delayed the output a few terms with a "smoother", but were capable of non-canonical outputs (0 or negative terms) following a term of truly newsworthy size. A continued fraction algorithm restricted to positive integer outputs would simply freeze on 1 2 2 2 ... times 1 2 2 2 ... . --rwg
Some funsters might not recognize Adam as the the author of the spectacular Life configuration that computes pi in decimal (and even displays the digits).
Thanks for the mention. I guess that some of the people on this list visited the Gathering for Gardner, where Tom Rokicki displayed it.
Maybe someday he can explain to us if and how he solved the ".999 problem", i.e., the absence of an a priori bound on the number of possible consecutive 9s or 0s, which, until they cease, leave the preceding digit unresolved (or equivalently, provoke negative or oversize "apology digits" following the premature estimate of an earlier one).
In order for that to occur, there must be a number of consecutive 9s or 0s linear in the position, so don't expect it to go wrong at the Feynman point! (Specifically, I think that there must be a string of n consecutive 9s or 0s between 3n and 4n digits.) A quick search on mathpuzzle.com confirms that the first 5T digits have been computed, and the last one is not a 9. So, the probability of my Pi machine computing incorrect digits is: sum[n = floor(5T/3) to infinity](10^-n) < 1/(10^10^12) (I think I'm pretty safe! : ) By the way, if that does happen, the output eventually returns to normal, as it cycles through the entire digit-generation algorithm for each decimal digit produced. The algorithm I used, by the way, is the one in Section 5 of this paper: http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf I managed to convert it into a list of 376 4-tuples, which is the native instruction format for my Life machines. (The algorithm uses 188 states, each of which has two possible decision branches.) Actually, the lookup table in the main body of the machine is a *flowchart*.
The corresponding problem with continued fraction output is the unboundedness of a term. Both Neil's and my calculations simply delayed the output a few terms with a "smoother", but were capable of non-canonical outputs (0 or negative terms) following a term of truly newsworthy size.
Oh, yes, you wanted a continued fraction version of my Pi machine, didn't you? I'll have to find a suitable algorithm, i.e. one that requires a finite number of integer registers, and takes polynomial time. If such an algorithm doesn't exist, then I would have to use my two- dimensional tape (capable of storing an unbounded number of integers) or a pairing function to allow a one-dimensional tape to emulate a two-dimensional tape. Sincerely, Adam P. Goucher
Links, please! I haven't found this pattern or any images or design descriptions, and I don't really know what to search for. I tried "adam life compute pi" and "golly pi calculator" and things like that. I found a few interesting things on pentadecathalon.com <http://pentadecathalon.com>Note that math-fun does not show embedded links. You have to show the URL literally. - Robert On Fri, Dec 24, 2010 at 08:07, Adam P. Goucher <apgoucher@gmx.com> wrote:
Some funsters might not recognize Adam as the the author of the
spectacular Life configuration that computes pi in decimal (and even displays the digits).
Thanks for the mention. I guess that some of the people on this list visited the Gathering for Gardner, where Tom Rokicki displayed it.
[...]
-- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com
Mainly to Robert: The initial pattern can be downloaded from here: http://calcyman.awardspace.co.uk/life-massive/pi.mc (376 KB) If you don't already have Golly, it is available at: http://golly.sourceforge.net I know that Dave Greene has iterated the pattern to 10^14 generations (14 decimal digits*), and Nathaniel Johnston has possibly simulated it slightly further. I have cross-posted this message to the Life List, in case anyone there has a copy of this file at 10^14 generations or later. (Both Dave and Nathaniel are active members of the Life List.) If anyone does have such a file, please could you send it to me? Sincerely, Adam P. Goucher * It is entirely a coincidence that it takes 10^14 generations to output 14 decimal digits, and does *not* take 10^N generations to output N decimal digits. Rather, it takes O(N^6) time (although initially O(N^4) time for small values of N).
---- Original Message ----
Links, please!
I haven't found this pattern or any images or design descriptions, and I don't really know what to search for. I tried "adam life compute pi" and "golly pi calculator" and things like that. I found a few interesting things on pentadecathlon.com
Note that math-fun does not show embedded links. You have to show the URL literally.
- Robert
Gosper and I attended a workshop on Symbolic Math systems in NYC, c. 1986. The Chudnovskys presented some transcendence-related results, including approximation bounds on pi^2 and pi. IIRC, the pi result was that |pi - p/q| > 1/q^13 with p & q integers, q>0. This provides a weak upper limit on the length of a block of 0s or 9s: the block can't be longer than 12 times the number of digits preceding the block. A similar result would apply to any repeating pattern like 123123123... Rich ------ Quoting "Adam P. Goucher" <apgoucher@gmx.com>:
Some funsters might not recognize Adam as the the author of the spectacular Life configuration that computes pi in decimal (and even displays the digits).
Thanks for the mention. I guess that some of the people on this list visited the Gathering for Gardner, where Tom Rokicki displayed it.
Maybe someday he can explain to us if and how he solved the ".999 problem", i.e., the absence of an a priori bound on the number of possible consecutive 9s or 0s, which, until they cease, leave the preceding digit unresolved (or equivalently, provoke negative or oversize "apology digits" following the premature estimate of an earlier one).
In order for that to occur, there must be a number of consecutive 9s or 0s linear in the position, so don't expect it to go wrong at the Feynman point! (Specifically, I think that there must be a string of n consecutive 9s or 0s between 3n and 4n digits.) A quick search on mathpuzzle.com confirms that the first 5T digits have been computed, and the last one is not a 9.
So, the probability of my Pi machine computing incorrect digits is:
sum[n = floor(5T/3) to infinity](10^-n)
< 1/(10^10^12)
(I think I'm pretty safe! : )
By the way, if that does happen, the output eventually returns to normal, as it cycles through the entire digit-generation algorithm for each decimal digit produced.
The algorithm I used, by the way, is the one in Section 5 of this paper:
http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf
I managed to convert it into a list of 376 4-tuples, which is the native instruction format for my Life machines. (The algorithm uses 188 states, each of which has two possible decision branches.)
Actually, the lookup table in the main body of the machine is a *flowchart*.
The corresponding problem with continued fraction output is the unboundedness of a term. Both Neil's and my calculations simply delayed the output a few terms with a "smoother", but were capable of non-canonical outputs (0 or negative terms) following a term of truly newsworthy size.
Oh, yes, you wanted a continued fraction version of my Pi machine, didn't you? I'll have to find a suitable algorithm, i.e. one that requires a finite number of integer registers, and takes polynomial time.
If such an algorithm doesn't exist, then I would have to use my two- dimensional tape (capable of storing an unbounded number of integers) or a pairing function to allow a one-dimensional tape to emulate a two-dimensional tape.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Adam P. Goucher -
Bill Gosper -
rcs＠xmission.com -
Robert Munafo