next up previous contents
Next: Real PCF Up: Functional approaches Previous: Turing-complete real number data

Partial real numbers and Turing-completeness

The same limitations arise in computation over the natural numbers; as it is well-known, the computable total functions are not recursively enumerable, so there cannot be any Turing-complete programming language that defines only total functions [50]. Kleene's idea was to generalize the notion of computable function to partial functions in order to obtain Turing-completeness results--the computable partial functions include the computable functions as a subset, but they are recursively enumerable. Similarly, it is possible add partial real numbers in order to obtain Turing-completeness results for abstract or built-in real number data types. A general theory of partiality in computation, known as domain theory, has been developed since the late 60's, initially by Dana Scott, and shortly after by many other people--see e.g. [1,2,31,39,45]. In this way, Turing-completeness for abstract or built-in data types for real number computation is possible. This has been developed only in the context of higher-order functional programming languages--as far as we know, no Turing-completeness theorems for imperative data types, in the presence of partial real numbers, has been proved or disproved.


next up previous contents
Next: Real PCF Up: Functional approaches Previous: Turing-complete real number data
Martin Escardo
2000-10-02