Admissible representations of effective cpo's (Q1068562)

In theoretical computer science studies, the notion of an effective cpo (complete partial order) is a very useful tool, especially in works devoted to semantics (see, among others, the work of D. Scott, G. Plotkin, M. Smyth, H. Egli and R. Constable). A cpo is an ''abstract'' object in general. A ''concrete'' machine cannot operate with such an object but only with names of objects. The authors define ''admissible representations'' for effective cpo's via two axioms which generalize the axioms for Gödel numberings of the partial recursive functions. By typological and recursion-theoretic considerations, they show that this definition is quite natural and the link between representations of a cpo D and the admissible numberings of \(D_{re}\), the set of all recursively enumerable elements of D. This article is clear and well-written and provides insight for further study of a theory of computational complexity for cpo functions. It would be of interest in connection with the notion of ''computation'', which plays a crucial role in theoretical computer science.