Date: Sep 16, 2012 2:16 PM
Author: Paul A. Tanner III
Subject: Re: Computing pi (or not)
On Sat, Sep 15, 2012 at 12:21 PM, Joe Niederberger
> Dave Renfro says:
>>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.
> OK , things have gotten a bit confused here and its my fault. Let me try to sort out a couple different threads.
>  I first barely sketched an idea alluding to an algorithm. It was intended to output something similar (as you say below) to 12345678910111213... (if you interpret the output as having a decimal point in front (or arrange the algorithm to print one) you have Champernowne's constant, which is one of the few provably normal numbers and its also transcendental.
>  Alternatively, you could interpret the output as writing out the nodes of an "infinite decimal tree".
> Each node is labelled with the "signature" of the path down to that node. Or since it was only a sketch of an idea, I was hoping people would accept that an algorithm exists that can (start) to output the infinite decimal tree complete with supporting edges, etc. The exact nature of the encoding is not important, nor is the node labeling. We could label nodes as I originally suggested or simply with the digits 0..9 and let the path back to the root recapture the digits for he finite decimal number we might want to associate with the node.
>  If you accept that the first N levels a such tree can be output by an algorithm, and left to run long enough it can go as deep as desired, we can say its outputting *all* the tree in principle (as we do with an algorithm that outputs the digits of pi - it never outputs all of pi, but we accept that in principle it could output as much of pi as desired given enough resources.) By tracing a suitable path down the generated tree we find also the digits of pi, clearly demarcated by the tree structures, as well as the beginning digits to every other real number (on different paths, or paths that will diverge later.)
> [A] Brain-teaser (I don't call this a paradox): the algorithm (which you have accepted, otherwise stop now)
> that is outputing the infinite decimal tree is also outputting paths corresponding to every real number. But we know some of those to be non-computable. But this looks *very* similar in priciple to the algorithm that just outputs the digits of pi. It outputs all those pi digits on a clearly delineated path and more.
> Why then does this not qualify as an algorithm to output
> all real number in the interval [0,10], in the same spirit as the algorithm that outputs the digits of pi?
Are you asking again what you asked before, which in
is "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"?"
look at the definition of a computable number:
"A real number a is said to be computable if it can be approximated by some computable function in the following manner: Given every positive integer n the function produces an integer k such that
(k - 1)/n =< a =< (k + 1)/n.
Why would you think that a binary tree or a variant is such that for every n and for every real number found in this tree a, there must be such a k?
------- End of Forwarded Message