|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
On the inversion of computable functions
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 . 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.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsDPMMS Pure Maths Seminar Cambridge Startup Weekend Big Data Forum talks series
Other talks‘Mixing It Up: A Blended Approach to Practice-based Research Training in Music’ Autumn Cactus & Succulent Show Strain And Thermal Expansion Coefficient Of Graphene Studied By Raman Spectroscopy Swiss depictions of regional costumes and landscapes: 1762-1840 Teaching in the Bed of Procrustes: Macho Culture and Gendered Teacher-Student Interactions in Secondary Education Is French Law Different from English Law?