BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:On the inversion of computable functions - Hoyrup\
, M (INRIA Paris - Rocquencourt)
DTSTART;TZID=Europe/London:20120703T140000
DTEND;TZID=Europe/London:20120703T150000
UID:TALK38882AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/38882
DESCRIPTION:Ergodic shift-invariant measures inherit many effe
ctive properties of\nthe uniform measure: for inst
ance\, the frequency of $1$'s in a typical\nsequen
ce converge effectively\, hence it converges at ev
ery Schnorr random\nsequence\; the convergence is
robust to small violations of randomness\n[1]\; ev
ery Martin-Lö\;f random sequence has a tail in
every\neffective closed set of positive measure [
2]. These\nproperties are generally not satisfied
by a non-ergodic measure\, unless\nits (unique) de
composition into a combination of ergodic measures
is\neffective. V'yugin [3] constructed a computab
le non-ergodic\nmeasure whose decomposition is not
effective. This measure is a countable\ncombinati
on of ergodic measures. What happens for finite co
mbinations? Is\nthere a finitely but non-effective
ly decomposable measure?\n\nWe prove that the answ
er is positive: there exist two non-computable\ner
godic measures $P$ and $Q$ such that $P+Q$ is comp
utable. Moreover\,\nthe set of pairs $(P\,Q)$ such
that neither $P$ nor $Q$ is computable\nfrom $P+Q
$ is large in the sense of Baire category.\n\nThis
result can be generalized into a theorem about th
e inversion of\ncomputable functions\, which gives
sufficient conditions on a one-to-one\ncomputable
function $f$ that entail the existence of a non-c
omputable\n$x$ such that $f(x)$ is computable.\n\n
We also establish a stronger result ensuring the e
xistence of a\n``sufficiently generic'' $x$ such t
hat $f(x)$ is computable\, in the\nspirit of Ingra
ssia's notion of $p$-genericity [4].\n\n[1] Vladim
ir V. V'yugin.\n"Non-robustness property of the in
dividual ergodic theorem."\n*Problems of Informa
tion Transmission*\, 37(2):27&ndash\;39\, 2001.
\n\n[2] Laurent Bienvenu\, Adam Day\, Ilya Mezhiro
v\, and Alexander Shen.\n"Ergodic-type characteriz
ations of algorithmic randomness."\nIn *Computab
ility in Europe (CIE 2010)*\, volume 6158 of *LNCS*\, pages 49&ndash\;58. Springer\, 2010.\n
\n[3] Vladimir V. V'yugin.\n"Effective convergence
in probability and an ergodic theorem for individ
ual random sequences."\n*SIAM Theory of Probabil
ity and Its Applications*\, 42(1):39&ndash\;50\
, 1997.\n\n[4] M.A. Ingrassia.\n*P-genericity fo
r Recursively Enumerable Sets.*\nUniversity of
Illinois at Urbana-Champaign\, 1981.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR