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