Re: Hardware random generators and nondeterminsm

In article <see-EE7DF6.09183403032008@xxxxxxxxxxxxxxx>,
Barb Knox <see@xxxxxxxxx> wrote:
Actually, in the usual formulations only a finite amount of tape is used
for "computing pi". The TM computes a function such as
Nth_Decimal_Digit_of_Pi(n) -- running the TM with the tape initially
containing some n, the TM halts with the tape containing the nth digit
of pi.

This is a tangential point, but note that Nth_Decimal_Digit_of_Pi is a
surprisingly subtle beast from a computational point of view. The point
is that you can certainly write down algorithms that compute a rational
number that is within epsilon of the true value of pi, but if you actually
want the Nth decimal digit of pi, then you have to deal with the case where
digits N+1, N+2, ... are all 9's. The obvious thing to do is to keep
computing until you get a non-9, but then to prove that this procedure
always halts you need to prove that pi is irrational---something I daresay
most people couldn't do without consulting a published proof.

For similar reasons it is much harder to prove that there is a polynomial
time algorithm for computing the Nth digit of pi than it is to prove that
there is a polynomial time algorithm for computing pi to an error of plus
or minus 10^(-N).
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.