
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 "noncomputable" 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 2place, > 3place 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 "noncomputable"?
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 nonconstructive 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

