COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > On the inversion of computable functions

## On the inversion of computable functionsAdd 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.”
[2] Laurent Bienvenu, Adam Day, Ilya Mezhirov, and Alexander Shen.
“Ergodic-type characterizations of algorithmic randomness.”
In [3] Vladimir V. V’yugin.
“Effective convergence in probability and an ergodic theorem for individual random sequences.”
[4] M.A. Ingrassia.
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. |
## Other listsRollo Davidson Lectures Machine Intelligence Lab Seminar Primary Care## Other talksIdentifying new gene regulating networks in immune cells Arriva Trains Wales by Tom Joyner Real Time Tomography X-Ray Imaging System - Geometry Calibration by Optimisation How to know Africa(s) in an age of youth hybridity Part Ib Group Project Presentations Ethics for the working mathematician, seminar 10: Mathematicians being leaders. |