|
|
Re: Computing pi (or not)
Posted:
Sep 14, 2012 12:11 PM
|
|
Joe Niederberger first wrote (in part):
http://mathforum.org/kb/message.jspa?messageID=7889637
> So I take it most people here know there are algorithms
> that can compute the digits of pi. And some of those may
> know about "non-computable" real numbers. And some may know
> a little programming (I assure you this is mathematical
> content however.) Its easy to create an algorithm that in
> turn spits out all 1 place decimal numbers, then all 2-place,
> 3-place and goes on forever (just like the algorithm that
> spits out pi digits.) So, if we visualize this output as a
> graph theory tree, which has 10 branches down at every vertex,
> and a sequence of digits (with an implicit decimal point
> after the first) can we not say this algorithm is outputting
> the digits of pi? (It certainly is, there is a path down the
> tree which shows the digits of pi in sequence!)
Joe Niederberger then wrote (in reply to my reply):
http://mathforum.org/kb/message.jspa?messageID=7890409
> The "infinite binary tree paradox" I can read about focuses
> on the cardinality of paths versus vertices. I could have
> been much clearer, but I am asking something different:
> if the algorithm is outputting all real numbers between
> [0,1], (or [0,10] etc. take your pick) then how can some/most
> of these be called "non-computable"?
I don't think "there exists a path down the tree" is evidence
that an algorithm exists. For any finite decimal, we can simply
take the single algorithm you alluded to that results in numbers
with that exact finite number of decimals. However, with only
the knowledge of these algorithms, you haven't described a way
of coming up with a single algorithm that would output a number
with an infinite number of decimals. Now it is true that there
are algorithms that output certain numbers with an infinite
number of decimals. For example, one such algorithm is to always
output 3, another is to encode one of the ways of computing the
digits of pi, and still another is to concatenate (in the appropriate
order) the algorithms you alluded to in order to output the
number 0.1234567891011121314...9899100101102103... Note that
this last number has every finite decimal string appearing
(infinitely many times, in fact), so we don't have to appeal
to faith as to whether pi has this property or to some other
way of coming up with such a number (such as using somewhat
non-constructive methods that are suggested from the comments
I made in my last post).
Given any set of finitely many algorithms, we can construct
a single algorithm whose outputs are the union of the outputs
of these finitely many algorithms. Thinking of "algorithm" as
a function from the positive integers to the positive integers,
and the finitely many algorithms being f_1, f_2, ..., f_N,
then we can define an algorithm g this way: g(1) = f_1(1),
g(2) = f_2(1), ..., g(N) = f_N(1), g(N+1) = f_1(2),
g(N+2) = f_2(2), ..., g(2N) = f_N(2), g(2N+1) = f_1(3),
g(2N+2) = f_2(3), ..., g(3N) = f_N(3), g(3N+1) = f_1(4), ...
Continuing in this way, it is clear that for each positive
integer k between 1 and N (inclusive) and for each positive
integer n, the value of f_k(n) will appear among the outputs
of the function g.
It is tempting to say that we can also do this with any
set of countably infinitely many algorithms, as follows.
Let f_1, f_2, f_3, ... be the algorithms. Then we can
define an algorithm g by diagonalizing through these
algorithms: g(1) = f_1(1), g(2) = f_1(2), g(3) = f_2(1),
g(4) = f_1(3), g(5) = f_2(2), g(6) = f_3(1), ... In other
words, start by grouping together the values of f_k(m)
when k + m takes on the constant values 1, 2, 3, ...
and then define g for the 1 case in which k + m = 1,
then define g for the 2 cases in which k + m = 2, then
define g for the 3 cases in which k + m = 3, etc.
Thus, we obtain a function g whose outputs include every
output of every one of the algorithms f_k.
In trying to carry out something like this in general
I believe there needs to be an algorithm that enumerates
the infinitely many algorithms. It's not enough to say
that if there are countably many, then we can enumerate
them, because for the above method to work it is essential
that a computable (recursive) enumeration of the algorithms
be available, so that the correspondence from positive
integer k to the k'th algorithm is itself an algorithm.
I believe it's a basic result in logic and computability
theory that the collection of algorithms (which are
countably infinite in number) cannot be enumerated so
that the correspondence from positive integer k to the
k'th algorithm is itself an algorithm.
Of course, in your case, we don't need to appropriately
enumerate all algorithms, but rather we only need to
appropriately enumerate those algorithms that arise in
your argument. However, I suspect that even for this
smaller set of algorithms, there does not exist an
enumeration of the type we need.
Dave L. Renfro
------- End of Forwarded Message
|
|
