Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!tuvie!nestroy!awiwuw11!nn1
From: NN1@awiwuw11.wu-wien.ac.at
Newsgroups: comp.theory
Subject: Re: do computers believe in real numbers?
Message-ID: <91090.154205NN1@awiwuw11.wu-wien.ac.at>
Date: 1 Apr 91 19:15:47 GMT
References: <7197@munnari.oz.au>
Organization: Wirtschaftsuniversitaet Wien, Vienna, Austria
Lines: 40

The issues addressed by A.E. Thomson are well-known, but let me
respond with some of the thoughts that come to my mind. First, there are
several equivalent ways to define the notion of computable real number.
A number a is computable, if the n-th digit of a is a recursive function
of n, or, equivalently, if the set of all rational numbers <= a is
recursive (assuming some coding scheme for rational numbers). Of course,
the computable real numbers form a countable subset of the set of real
numbers. Concerning the question in what sense noncomputable real numbers
exist: Here the answer will of course depend on the philosophical view
one takes on the foundations of mathematics. Here is just one example:
consider the number a_0.a_1 a_2 a_3 ... where a_i equals 1, if i is a
Fermat exponent, and  0 otherwise. This number may or may not be
computable, since it is an open problem whether or not one can effectively
decide for given i if i is a Fermat exponent. My personal view is the
classical Platonistic one, and I would consider this as an acceptable
definition of a real number, even though it does not provide a method for
finding out if the number equal to or larger than 0.11 . This is just an
open problem, just as there are other open problems. I know, however,
that some mathematicians take a different view.
Now for the more practical quesiton raised by A.E. Thomson, how real
numbers should indeed be represented on a computer, so that at any stage
one can get as many digits as requested, but little work is done as long
as many digits are not needed. Well, I do not know precisely enough what
is really needed, but at first glance it looks like the best thing would
be to work with symbolic expressions for reals, like sqrt(2). All common
Computer Algebra Systems work with such expressions. One may consider
many classes of expressions, corresponding to different subsets of the
reals, the smallest one to be reasonably considered is the set of all
rational numbers, the largest that of computable real numbers. In the
latter case a program to compute the i-th digit from i or something
similar would have to be considered as the symbolic expression, but
this is certainly not practical. The computable numbers include all
algebraic numbers, but also numbers like pi, e, 2^sqrt(2), ln 5 etc.
If A.E. Thomson needs something more powerful than floating point
expressions, but less complicated than a computer algebra system, then
the only thing that comes to my mind would be to work with a rather
restricted class of expressions.

Heinrich Rolletschek
k310670@AEARN