Genericity of weakly computable objects

Mathieu Hoyrup 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In computability theory many results state the existence of objects that in many respects lack algorithmic structure but at the same time are effective in some sense. Friedberg and Muchnik's answer to Post problem is one of the most celebrated results in this form. The main goal of the paper is to develop a general result that embodies a large number of these particular constructions, capturing the essential idea that is common to all of them, and expressing it in topological terms. To do so, we introduce the effective topological notions of irreversible function and directional genericity and provide two main results that identify situations when such constructions are possible, clarifying the role of topology in many arguments from computability theory. We apply these abstract results to particular situations, illustrating their strength and deriving new results.This paper is an extended version of a conference paper with detailed proofs and new results.
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2017, Special Issue: Theoretical Aspects of Computer Science, 60 (3), 〈10.1007/s00224-016-9737-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01095864
Contributeur : Mathieu Hoyrup <>
Soumis le : vendredi 9 décembre 2016 - 12:44:57
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : jeudi 23 mars 2017 - 09:53:49

Fichier

revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Mathieu Hoyrup. Genericity of weakly computable objects. Theory of Computing Systems, Springer Verlag, 2017, Special Issue: Theoretical Aspects of Computer Science, 60 (3), 〈10.1007/s00224-016-9737-6〉. 〈hal-01095864v2〉

Partager

Métriques

Consultations de la notice

161

Téléchargements de fichiers

45