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: Signed-digit notation
Up: Introduction to EXACT NUMERICAL
Previous: Realizers
Martin Escardo
2000-10-02