skip to content

On the inversion of computable functions

Presented by: 
M Hoyrup INRIA Paris - Rocquencourt
Tuesday 3rd July 2012 - 14:00 to 15:00
INI Seminar Room 1
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 [1]; every Martin-Löf random sequence has a tail in every effective closed set of positive measure [2]. 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 [3] 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 [4].

[1] Vladimir V. V'yugin. "Non-robustness property of the individual ergodic theorem." Problems of Information Transmission, 37(2):27–39, 2001.

[2] 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.

[3] 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.

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

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons