Computation is Exclusive

A "computable number" is defined as a number for which a finite 
machine with a finite program exists whose output converges on 
that number.  Notice that we don't require the number to ever be 
completely computed, but merely that the output of the program 
converges on that number.  For example, numbers such as sqrt(2) 
and PI and e are considered computable, because we can specify 
finite programs that converge on these values.

When discussing "computable numbers" we usually argue that the
quantity of such numbers is necessarily countable, because a
computable number is defined to be a number that is implied by
a finite machine with a finite program (written with a finite
number of characters), and such machines and programs are obviously
countable.  However, we should perhaps qualify this, so that
"computable" is understood to mean "deterministically computable", 
or maybe a better term would be "repeatably computable".  A non-
deterministic computer (such as a machine printing out a string of
binary digits 0.10011101... based on a sequence of coin tosses or
quantum mechanical processes, has as its range of possible outputs 
every real number.  Of course, with such a machine we can't say
in advance to what value the output converges, but is it correct
to say that, therefore, the output does not converge?

We can't conceptually extrapolate the output of such a machine to 
infinity, so we can't talk about convergence in the usual way.  All
we ever have from a random process are the results already produced.
The "ultimate" result of the process never "exists", at least not in 
the same first-order Platonic sense that the ultimate result of a 
PI-computing algorithm "exists" and is implicit in the algorithm.  
For a random process, all numbers are equally implicit, and one 
particular number only gets singled out on a finite basis as the 
digits are formed.

This illustrates that the essence of computation is exclusive, not 
inclusive.  We never actually construct a real number such as PI.  
As we ADD digits we simply EXCLUDE all but a smaller and smaller 
range of possibilities.  All knowledge (from a sufficiently robust
point of view) is exclusive in nature, sort of like the idea that
a statue is already "there" in the raw block of stone, and all the
sculptor does is remove the surrounding material.

Return to MathPages Main Menu
Сайт управляется системой uCoz