UP

Not-So-Good Candidates

First we start with non-candidates just to put on record the obvious reasons why they don't solve the problem.

Rationals

Arbitrary Precision Floating Point

Automatic Reals

N-ary expansions for some N>1

Continued Fractions

Rationals

Technically these fail because they are a proper subset of the computable numbers. In practice a perfect implementation of rationals still suffers from the same problems which caused the real numbers to be introduced, known since the times of the Greeks. Some problems that we want answers to just don't have rational solutions, so we end up having to accept approximations.

Arbitrary Precision Floating Point

There's some scope for variation in what you mean by this. In the best case that I can imagine you are still just representing the rational numbers so the previous observations apply.

Automatic Reals

This is an interesting middle ground which is the subject of some research. I think they are something like the set of reals whose n-ary expansions are computable by some device less powerful than a turing machine. John Doner has some Web material on them to which I will place a reference if I can find it again!

As I understand it, again these systems fail simply because they don't represent all the computable reals. A consequence of this is that they don't have very good closure properties.

Computable N-ary expansions for some N>1

This is the first candidate for which the set of reals represented is the computable reals. Unfortunately it is also the first to demonstrate that meeting that criterion is not sufficient.

Computable Continued Fractions

These are neat. See Knuth, Volume 2, page 316 [1st Edition; s.4.5.3, p. 339 in 2nd Edition], and Gosper.

They not only represent all the real numbers, they do so uniquely (if you are using regular continued fractions). Furthermore, the rationals are represented by finite continued fractions.

Unfortunately the combination of these two features is sufficient to guarantee that addition is not effective over this representation (a general algorithm for adding arbitrary regular continued fractions will end up looping without producing any more terms if you apply it to two irrational numbers whose sum is rational).

Possibly you might get an admissible representation by using irregular continued fractions, but then you lose the uniqueness.

You can still use them as a part of an admissible representation (e.g. as a way of representing rationals in a convergent sequence). Or you can use them and put up with occasional non-termination. But anyway, they are inadmissible.

N-ary Expansion Representations

Minsky defines a computable real as one whose decimal (or n-ary) expansion can be "generated sequentially by a turing machine". This definition is suggestive of a representation of computable reals as algorithms for generating positional expansions. Unfortunately, under this representation, the operation of addition is not itself computable.

Consider two algorithms as follows. The first computes the decimal expansion "0.1111111..." and the second the expansion "0.8888...". An algorithm to compute the expansion of the sum of these numbers cannot determine the expansion by evaluating the algorithms which generate the two operands, since this would never yield sufficient information to determine the first digit of the result. It would therefore have to inspect the algorithms and discover in some way the result. In doing so it would effectively be computing whether two algorithms were computing the same number. From such an algorithm a solution to the halting problem could be constructed.

Continued Fractions

For an explanation of continued fractions and an extended account of their merits see: Henry Baker's Continued Fractions Page

Now I have a problem with continued fractions. Basically, they don't work. Addition is not effective over reals represented as continued fractions. Now Veuillemin acknowledges this in his paper, and then he goes right ahead and uses them anyway. So he must have some trick up his sleeve, and I havn't yet looked close enough to figure out what it is. (e.g. he could use a continued fraction plus an error bound, or a pair of continued fractions, not that I think either of these is a good idea, but they probably could be made to work.)

UP HOME © RBJ created 1995/9/3 modified 1998/7/17