# SAS

## Seminar

### On the inversion of computable functions

Seminar Room 1, Newton Institute

#### Abstract

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.

## Comments

Start the discussion!