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 talksRetinal mechanisms of non-image-forming vision Part Ib Group Project Presentations How to know Africa(s) in an age of youth hybridity Real Time Tomography X-Ray Imaging System - Geometry Calibration by Optimisation Arriva Trains Wales by Tom Joyner Identifying new gene regulating networks in immune cells To be confirmed The frequency of ‘America’ in America Black and British Migration Picturing the Heart in 2020 Inferring the Evolutionary History of Cancers: Statistical Methods and Applications Ethics for the working mathematician, seminar 10: Mathematicians being leaders. |