Irreversible computable functions

Mathieu Hoyrup 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The strong relationship between topology and computations has played a central role in the development of several branches of theoretical computer science: foundations of functional programming, computational geometry, computability theory, computable analysis. Often it happens that a given function is not computable simply because it is not continuous. In many cases, the function can moreover be proved to be non-computable in the stronger sense that it does not preserve computability: it maps a computable input to a non-computable output. To date, there is no connection between topology and this kind of non-computability, apart from Pour-El and Richards ''First Main Theorem'', applicable to linear operators on Banach spaces only. In the present paper, we establish such a connection. We identify the discontinuity notion, for the inverse of a computable function, that implies non-preservation of computability. Our result is applicable to a wide range of functions, it unifies many existing ad hoc constructions explaining at the same time what makes these constructions possible in particular contexts, sheds light on the relationship between topology and computability and most importantly allows us to solve open problems. In particular it enables us to answer the following open question in the negative: if the sum of two shift-invariant ergodic measures is computable, must these measures be computable as well? We also investigate how generic a point with computable image can be. To this end we introduce a notion of genericity of a point w.r.t. a function, which enables us to unify several finite injury constructions from computability theory.
Type de document :
Communication dans un congrès
STACS - 31st Symposium on Theoretical Aspects of Computer Science - 2014, Mar 2014, Lyon, France. 2014
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
Contributeur : Mathieu Hoyrup <>
Soumis le : mardi 14 janvier 2014 - 11:09:08
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : mardi 15 avril 2014 - 16:19:00


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00915952, version 4



Mathieu Hoyrup. Irreversible computable functions. STACS - 31st Symposium on Theoretical Aspects of Computer Science - 2014, Mar 2014, Lyon, France. 2014. 〈hal-00915952v4〉



Consultations de la notice


Téléchargements de fichiers