Next: Real PCF
Up: Functional approaches
Previous: Turing-complete real number data
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: Real PCF
Up: Functional approaches
Previous: Turing-complete real number data
Martin Escardo
2000-10-02