On the inversion of computable functions

Add to your list(s) Download to your calendar using vCal

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

If you have a question about this talk, please contact Mustapha Amrani.

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

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

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.