Rekursionstheorie und Komplexitätstheorie auf effektiven CPO-S

Weihrauch, Klaus

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.

Vorschau

Zitieren

Zitierform:

Weihrauch, Klaus: Rekursionstheorie und Komplexitätstheorie auf effektiven CPO-S. Hagen 1980. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe