next up previous contents
Next: Signed-digit notation Up: Introduction to EXACT NUMERICAL Previous: Realizers

     
Alternative notations

The proposed solutions to this computational problem of decimal notation include the adoption of the following alternative notations for real numbers:

1.
Base 2/3 with digits 0 and 1.

(Brouwer 1920, Turing 1937b)

2.
Any integral base with negative digits. (Leslie 1817, Cauchy 1840, Avizienis 1964, Wiedmer 1980)

3.
Nested sequences of rational intervals.

(Grzegorczyk 1957)

4.
Cauchy sequences of rationals with fixed rate of convergence. (Bishop 1967 )

5.
Continued fractions.

(Vuillemin 1988)

6.
Base Golden Ratio with digits 0 and 1.

(Di Gianantonio 1996)

7.
Infinitely iterated Möbius transformations.

(Edalat and Potts 1997)

These proposed notations are all equivalent, in the sense that one can effectively translate between them. This is sometimes formulated as a ``Church-Turing Thesis'' for real number computation. For example, the basic operations, the trigonometric and logarithmic functions, and many functions that occur in analysis are computable with respect to these notation systems.

Topologically, these systems are characterized as maximal in the following sense: given any other notation system for the reals for which the denotation map is a topological quotient, there is a continuous translation from any of the above notations [36,63]. For example, decimal notation is not maximal, because it is not possible to continuously translate signed-digit decimal to standard decimal notation--if it were, then it would be possible to continuously multiply by three in decimal notation, which contradicts Proposition 6.4.



 
next up previous contents
Next: Signed-digit notation Up: Introduction to EXACT NUMERICAL Previous: Realizers
Martin Escardo
2000-10-02