Zulässige CPO's - ein Entwurf für ein allgemeines Berechenbarkeitskonzept.

Christoph Kreitz.

Diplomarbeit, RWTH Aachen, 1981.   (German)


Computability theory in complete partial orders (cpo's) has been studied by several authors. In this paper we introduce "admissible cpo's" as a generalization of Sciore and & Tang's "admissible P-domains" and study computability theory in them. An admissible cpo is characterized by an effective basis of the cpo and an effective topological base. Computable elements of an admissible cpo are defined and, as a generalization of Rogers' Isomorphism Theorem for Gödel numberings of the partial-recursive functions, it is shown that two "effective numberings" of the computable elements are recursively isomorphic. For computable functions a generalization of the Myhill-Shepherdson theorem is proved. We show that admissible cpo's are closed under product, function space, and computable retracts. Finally, we compare our concept with the computability concepts of Kanda & Park's recursive cpo's, Sciore & Tang's admissible P-domains, and Smyth's effectively given domains and show that our computability theory concept is the most general one.

Not available online   Send an email to to receive a hard copy BACK
Back to overview of papers

Bibtex Entry

@MastersThesis{mt:Kreitz81a, author = "Christoph Kreitz", title = "{Zul{\"a}ssige CPO's - ein Entwurf f{\"u}r ein allgemeines Berechenbarkeitskonzept}", school = "RWTH Aachen", year = "1981" }