next up previous contents
Next: Partial real numbers and Up: Functional approaches Previous: Functional approaches

Turing-complete real number data types

By a Turing-complete data type it is meant a data type for which all computable operations are definable from the operations available in the interface. Boehm and Cartwright [12] argue that there cannot be any Turing-complete abstract data type for real numbers. Accepting the fact that the computable real numbers are enumerable but not recursively enumerable, by an argument which is essentially the same as Cantor's argument of uncountability of the real numbers, it is easy to see why this is the case.



Martin Escardo
2000-10-02