Re: Closer and closer you move to the Cantorian cliff

• Previous message: el goog: "Re: Qustion about minimum (k, n-k)-cut in a graph"
• Next in thread: Michel Hack: "Re: Closer and closer you move to the Cantorian cliff"
• Reply: Michel Hack: "Re: Closer and closer you move to the Cantorian cliff"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: Wed, 23 Mar 2005 14:05:18 -0800

http://groups.google.co.in/groups?selm=1105863295.677791.34430%40z14g2000cwz.googlegroups.com
> Date: 16 Jan 2005 00:14:55 -0800
(Sorry for tardy reply but the mouse on my computer stopped working so
 I had no way to do hardly anything online until today.)
> From: "george" <greeneg@cs.unc.edu>
> OBViously no finite machine running for finite time on finite input
> "generates" the infinite decimal expansion of ANY irrational number,
> computable.or not.

That's correct but irrelevant. I never made any such claim. My claim
was that a machine might sit computing for a very long time, churning
out successive digits as time goes on, so that the longer the machine
is allowed to run the more digits are generated. Mathematically we say
that there's an infinite sequence of digits, where the machine computes
an initial segment that grows with time to include every element of the
digit sequence eventually. (For each digit of infinite sequence, that
digit will eventually be reached.) If so, the infinite sequence is
"computable".

Alternately, a machine might be given as input a number which specifies
how many digits are desired and the machine the generates exactly that
many digits. The restriction is that given two different inputs m < n,
the digits generated from m exactly match the first m digits generated
from n. The union of all those overlapping initial sequences defines
the mathematical infinite sequence. Likewise that infinite sequence is
"computable".

Alternately, a machine might be given as input the number of digits of
precision to use internally, and then generate whatever number of
digits of output are forced by those internal computations. Two
restrictions: (1) As internal precision gets arbitrary large, output
gets arbitrarily large, i.e. limit(prec->inf)(output) = inf. (2)
Initial-segment match as above. Likewise union of overlapping initial
segments is mathematical infinite sequence which is "computable".

> That is not even what "computable" means.

Horsefeathers! All of the above three definitions of computable
infinite sequence are equivalent, each of which is equivalent to the
definition you give below:

> The w-wide real is "computable" iff there exists a TM that given N as
> input, produces the digit in the Nth position as output. THAT IS HOW
> you allow a finite TM to "compute"/represent an infinite string.

That is yet another definition, equivalent to the three I gave. Do you
disagree that given any machine satisfying any of the four definitions
(i.e. computing single digits or initial segments or growing unbounded
initial segment), it's possible to build a machine that emulates the
first machine internally to produce an overall machine satisfying any
of the remaining three definitions?

> That is how we know Pi is computable.

Actually not. The third definition, namely determine beforehand the
internal precision, then run it and get some smaller number of output
digits, with internal precision increased signficantly every few years
yielding corresponding significant increase in output sequence length.
Only an idiot would spend large amounts of computer time just to
compute a single million(-some-odd)th digit and discard all the
previous digits, then go through even more work to compute a single
million(-some-odd-plus-one)th digit again discarding all previous
digits, etc.

Note also that there is no known way to generate the nth digit of pi
without in fact generating all or most of the earlier digits at the
same time, or at least generating all the information necessary to
generate those earlier digits. In fact usually the calculations are
done in binary in the first place, generating all or most of the bits
in an approximation to pi, then that approximation is used to generate
the decimal digits corresponding to it. If you really only want a
single digit, I suppose you could generate the binary approximation and
then use a finite-state modular algorithm to directly generate just the
single desired digit without actually generating all the earlier
digits.

• Previous message: el goog: "Re: Qustion about minimum (k, n-k)-cut in a graph"
• Next in thread: Michel Hack: "Re: Closer and closer you move to the Cantorian cliff"
• Reply: Michel Hack: "Re: Closer and closer you move to the Cantorian cliff"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]