KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
DOI: 10.5445/IR/54199

Topological aspects of numberings

Menzel, Wolfram; Stephan, Frank

We investigate connections between the syntactic and semantic
distance of programs on an abstract, recursion theoretic level.
For a certain rather restrictive notion of interdependency of
the two kinds of distances, there remain only few and
"unnatural" numberings allowing for such close relationship.
Weakening the requirements leads to the discovery of universal
metrics such that for an arbitrary recursively enumerable family
of functions a numbering compatible with such a metric can
uniformly be constructed. We conclude our considerations with
some implications on learning theory.

Zugehörige Institution(en) am KIT Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Forschungsbericht
Jahr 1999
Sprache Englisch
Identifikator ISSN: 1432-7864
URN: urn:nbn:de:swb:90-AAA541994
KITopen-ID: 54199
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 1999,15
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page