Stability and computability in coherent domains

The relation between stability and sequentiality is investigated in the category of Girard's coheent domains. We introduce and discuss a notion of computability for stable functions based on the recursive enumerability of their traces, in a way similar to the definition of computable functions in Scott's effectively given domains. We then relate this notion of computability to regular sets and relative algorithms (oracle-machines) of the theory of relativized computability. The notion of oracle-machine is used to formalize the idea of a main sequential program which calls an unspecified external agent O (a sort of subroutine call). In particular we prove that a function f between two coherent domains X and Y is stable and computable if and only if f may be computed by an oracle-machine questioning “in a positive way” a simple class of oracles that supply informations about elements in X.

Authors

• Andrea Asperti

Keywords

No keywords are indexed for this paper.