Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00915952
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Tuesday, January 14, 2014 - 11:09:08 AM
Last modification on : Saturday, June 25, 2022 - 7:46:41 PM
Long-term archiving on: : Tuesday, April 15, 2014 - 4:19:00 PM

File

stacs.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00915952, version 4

Collections

Citation

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

Share

Metrics

Record views

345

Files downloads

238