Rekursionstheorie und Komplexitätstheorie auf effektiven CPO-S
Effective cpo-s are a useful tool for introducing computability on a large class of sets. In this report Blum's theory of computational complexity is generalized to certain effective cpo-s with effective weight. At first, as a generalization of Rogers's Isomorphism Theorem for Gödel numberings of the partial recursive functions it is proved that two "admissible numberings" of the recursively enumerable elements of an effective cpo are recursively isomorphic. The concept of effective weight on an effective cpo is introduced and recursive cpo-elements are defined. In analogy to Blum's approach two axioms for cpo-complexity are introduced. For cpo-elements with zero weight a hierarchy theorem, the speedup theorem and the gap theorem are proved. Using "extended" cpo-s the results can be applied to the recursive elements of a cpo.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten