FOM: Precision and Turing-computability

[D Richardson]

On Wed, 29 May 2002, Insall wrote:

> On 29 May 2002, Daniel Richardson wrote:
> ``It may be that exact computation is quite possible for the real numbers of
> classical analysis (which are only a small subset of computable reals).''
> 
> I would like to know which ``computable reals'' are not ``real numbers of
> classical analysis''.  

This is a fairly well known idea.  For example, in Serge Lang's
Introduction to Transcendental Number Theory, he says that the numbers of
classical analysis are those obtained from the rationals using exp, log
and algebraic operations.  These would be complex numbers of classical
analysis.  Most transcendental number theory is about this small subset of
computable reals.  Most of the numbers which play crucial roles in
applications are also in this subset.  


To me, classical analysis (generally) proves theorems
> about ``the real numbers'', as many quotes from various sources would seem
> to indicate.  (Frequently, theorems are formulated as ``Let r be a real
> number...'', but usually not ``Let r be a real number of classical
> analysis...''.  I was not aware that any of the classical analysts thought
> that when they claimed to be working with ``the real numbers'' they were
> actually working with ``only a small subset of computable reals''.)
> 
> The symbolic calculation to which much of the rest of your post refers is
> also possible for arbitrary real numbers.  Consider, for example, the
> reduction of the expression ``x-x=0''.  For which real numbers can this fail
> to be exactly verified by a symbolic processor, such as that employed by
> MathCad, or by Maple, or by Mathematica?  I'd say none, because the
> processor has been provided with enough axioms for real number arithmetic to
> allow perfect, exact, complete computation for ``x-x'' as an ``expression''.
> (The field axioms are more than enough, and comprise a small amount of the
> information we know about all of the real numbers, not just ``the computable
> ones''.)
> 
There are two points here.  First, the computable real (or complex )
numbers do not form a effective field.  I mean that we can not decide
equality.  Of course most mathematics and most  algorithms actually need
equality.  My claim is is that computable reals do not form a nice
algebra.   For this reason it is important philosophically and practically
to find good subfields of the computable reals or complutable complex
numbers in which the equality problem can be decided (or even easily
decided).  A lot of work has gone in to this.  In computational geometry
for example, it is not useful to think of real numbers as either
represented by Turing machines, or by decimal approximations; but it is
reasonable to work in the field of real algebraic numbers, which are all
defined in a standard way by polynomial equations.

The second point is that the equality problem involves more than just
deciding x-x =0.  More than just field axioms are needed.  Of course
current computer algebra systems do attempt to solve this problem, and
they do solve part of it but not all of it.  Even recognizing equalities
in nested radicals may be fairly hard.  

Daniel Richardson