On the inversion of computable functions

Abstract

The question of the computability of diverse operators arising from mathematical analysis has received a lot of attention. Many classical operators are not computable, and the proof often does not resort to computability theory: the function under consideration is not computable simply because it is not continuous. A more challenging problem is then its computable invariance: is the image of every computable point computable? Very often it happens that it is not the case, and the proof is usually much more evolved, based on computability-theoretic constructions. This empirical observation raises the following question: is it a coincidence that discontinuous functions often happen to be non-computably invariant? Or do these functions share a strong form of discontinuity that prevents them to be computably invariant? A positive answer was brought by Pour-El and Richards through their so-called ''First Main Theorem'': for to certain classes of closed linear operators continuity is equivalent to computable invariance. In this paper, we focus on inverses of computable functions and introduce a discontinuity notion that prevents computable invariance. This result is applicable in many situations, unifies many ad hoc constructions and sheds light on the relationship between computability and continuity. The strength of this result lies in the fact that verifying that a function satisfies the property is much easier than disproving its computable invariance. We then present two applications of our main result. First 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? Second, it enables to significantly improve Pour-El and Richards First Main Theorem by requiring the graph of the linear operator to be an effective G_delta-set instead of a closed set.

Locations

• HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF