Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!tuvie!nestroy!awiwuw11!nn2
From: NN2@awiwuw11.wu-wien.ac.at
Newsgroups: comp.theory
Subject: Re: do computers believe in real numbers? (slight return)
Message-ID: <91102.130159NN2@awiwuw11.wu-wien.ac.at>
Date: 14 Apr 91 13:38:42 GMT
References: <7285@munnari.oz.au>
Organization: Wirtschaftsuniversitaet Wien, Vienna, Austria
Lines: 72

In an earlier article I gave the following two characterizations of
computable real numbers: a is computable if it satisfies

(alpha) The n-th digit of a is a recursive function of n

or, equivalently,

(beta) The set of rational numbers q < a is recursive.

To these definitons Frank Silberman had the following objection:

>        One difficulty with this definition would be the problem of
>        asking for the first 5 mantissa digits of an expression that
>        simplifies to 0.99999 ...
>        Clearly, the result equals 0.1 exactly, so the first five
>        mantissa digits OUGHT to be 0.10000, yet, most naive systems
>        would report 0.9999 !!! If computation with real numbers is to be
>        "computable," we need a more lenient requirement than "ability to
>        compute any single digit in a finite amount of time," and we need
>        a more lenient notion of approximation than "truncation of the
>        digits."

Let me briefly comment on this objection.

1. Let me first point out that the above definition of computable real
   number is not my own. Characterization (alpha) is from

     Turing: On computable numbers with an application to the Entscheidungs-
     problem. Proc. London Math. Soc. 42 (1936).

2. It is a simple exercise to show that (beta) is equivalent to (alpha).
   This does not mean one representation of a can be effectively transformed
   into the other. The truth is that a program for deciding for given b, c
   can be effectively transformed into a program for computing the n-th digit
   of a, but not vice versa.

3. The definition of computable real number a only reflects a computability
   property of a itself. It is a different matter to define computable
   functions on real numbers. The obvious approach is to call a real function
   f computable iff a representation of c computable number a can be
   effectively transformed into a representation of f(a), but then the
   question whether or not f is computable depends on the kind of
   representation used. For instance, if the representation of a is a program
   which decides if a given rational number is smaller than, equal to or
   larger than a, then addition, subtraction etc. are computable. However, if
   the prgram only decides if a given rational is smaller than a or >= a, then
   subtraction is already non-computable.

4. What Frank Silberman actually says with his objection isthat not every
   representation of a can be effectively transformed into every other.
   We may call a representation system S1 more lenient than S2 (and S2 more
   rigorous than S1), if there is a translation from S2 to S1, but not from
   S1 to S2. For instance if representation S1 of a is a program which
   computes the n-th digit of a from n, assuming that the decimal
   representation 0.10000 ... and 0.09999 ... are both acceptable, and
   representation S2 is a program which decides if a given rational is
   smaller than, or >= a, then S1 is more lenient than S2. This is no longer
   true if in S1 only 0.1000 ... is considered an acceptable decimal
   representation, but it is again true if in S2 the program makes a
   threeway decision if a rational is < a, = a or > a. The situation is
   comparable with the representation of finite sets by various types of
   indices: here the representation by a canonical index is more rigorous
   than the one by a characteristic index, which in turn is more rigorous
   than the one by an r.e. index.

5. While it is not clear which representation of reals is the `right one,'
   it is clear that the notion of computable real is not very practical
   to work with. It is surely preferable not to represent all, but only
   some computable reals on the computer.

Heinrich Rolletschek
K310670@AEARN