Hoyrup, Mathieu
Irreversible computable functions
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 noncomputable in the stronger sense that it does not preserve computability: it maps a computable input to a noncomputable output. To date, there is no connection between topology and this kind of noncomputability, apart from PourEl 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 nonpreservation 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 shiftinvariant 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.
BibTeX  Entry
@InProceedings{hoyrup:LIPIcs:2014:4471,
author = {Mathieu Hoyrup},
title = {{Irreversible computable functions}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {362373},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4471},
URN = {urn:nbn:de:0030drops44712},
doi = {10.4230/LIPIcs.STACS.2014.362},
annote = {Keywords: Computability theory, computable analysis, finite injury, generic set}
}
2014
Keywords: 

Computability theory, computable analysis, finite injury, generic set 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

2014 