# On the inversion of computable functions

• Hoyrup, M (INRIA Paris - Rocquencourt)
• Tuesday 03 July 2012, 14:00-15:00
• Seminar Room 1, Newton Institute.

Semantics and Syntax: A Legacy of Alan Turing

Ergodic shift-invariant measures inherit many effective properties of the uniform measure: for instance, the frequency of \$1\$’s in a typical sequence converge effectively, hence it converges at every Schnorr random sequence; the convergence is robust to small violations of randomness every Martin-Löf random sequence has a tail in every effective closed set of positive measure . These properties are generally not satisfied by a non-ergodic measure, unless its (unique) decomposition into a combination of ergodic measures is effective. V’yugin  constructed a computable non-ergodic measure whose decomposition is not effective. This measure is a countable combination of ergodic measures. What happens for finite combinations? Is there a finitely but non-effectively decomposable measure?

We prove that the answer is positive: there exist two non-computable ergodic measures \$P\$ and \$Q\$ such that \$P+Q\$ is computable. Moreover, the set of pairs \$(P,Q)\$ such that neither \$P\$ nor \$Q\$ is computable from \$P+Q\$ is large in the sense of Baire category.

This result can be generalized into a theorem about the inversion of computable functions, which gives sufficient conditions on a one-to-one computable function \$f\$ that entail the existence of a non-computable \$x\$ such that \$f(x)\$ is computable.

We also establish a stronger result ensuring the existence of a ``sufficiently generic’’ \$x\$ such that \$f(x)\$ is computable, in the spirit of Ingrassia’s notion of \$p\$-genericity .

 Vladimir V. V’yugin. “Non-robustness property of the individual ergodic theorem.” Problems of Information Transmission, 37(2):27–39, 2001.

 Laurent Bienvenu, Adam Day, Ilya Mezhirov, and Alexander Shen. “Ergodic-type characterizations of algorithmic randomness.” In Computability in Europe (CIE 2010), volume 6158 of LNCS , pages 49–58. Springer, 2010.

 Vladimir V. V’yugin. “Effective convergence in probability and an ergodic theorem for individual random sequences.” SIAM Theory of Probability and Its Applications, 42(1):39–50, 1997.

 M.A. Ingrassia. P-genericity for Recursively Enumerable Sets. University of Illinois at Urbana-Champaign, 1981.

This talk is part of the Isaac Newton Institute Seminar Series series.