BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the inversion of computable functions - Hoyrup\, M (INRIA Paris
  - Rocquencourt)
DTSTART:20120703T130000Z
DTEND:20120703T140000Z
UID:TALK38882@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Ergodic shift-invariant measures inherit many effective proper
 ties of\nthe uniform measure: for instance\, the frequency of $1$'s in a t
 ypical\nsequence converge effectively\, hence it converges at every Schnor
 r random\nsequence\; the convergence is robust to small violations of rand
 omness\n[1]\; every Martin-L&ouml\;f random sequence has a tail in every\n
 effective closed set of positive measure [2]. These\nproperties are genera
 lly not satisfied by a non-ergodic measure\, unless\nits (unique) decompos
 ition into a combination of ergodic measures is\neffective. V'yugin [3] co
 nstructed a computable non-ergodic\nmeasure whose decomposition is not eff
 ective. This measure is a countable\ncombination of ergodic measures. What
  happens for finite combinations? Is\nthere a finitely but non-effectively
  decomposable measure?\n\nWe prove that the answer is positive: there exis
 t two non-computable\nergodic 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\nTh
 is result can be generalized into a theorem about the inversion of\ncomput
 able functions\, which gives sufficient conditions on a one-to-one\ncomput
 able function $f$ that entail the existence of a non-computable\n$x$ such 
 that $f(x)$ is computable.\n\nWe also establish a stronger result ensuring
  the existence of a\n``sufficiently generic'' $x$ such that $f(x)$ is comp
 utable\, in the\nspirit of Ingrassia's notion of $p$-genericity [4].\n\n[1
 ] Vladimir V. V'yugin.\n"Non-robustness property of the individual ergodic
  theorem."\n<i>Problems of Information Transmission</i>\, 37(2):27&ndash\;
 39\, 2001.\n\n[2] Laurent Bienvenu\, Adam Day\, Ilya Mezhirov\, and Alexan
 der Shen.\n"Ergodic-type characterizations of algorithmic randomness."\nIn
  <i>Computability in Europe (CIE 2010)</i>\, volume 6158 of <i>LNCS</i>\, 
 pages 49&ndash\;58. Springer\, 2010.\n\n[3] Vladimir V. V'yugin.\n"Effecti
 ve convergence in probability and an ergodic theorem for individual random
  sequences."\n<i>SIAM Theory of Probability and Its Applications</i>\, 42(
 1):39&ndash\;50\, 1997.\n\n[4] M.A. Ingrassia.\n<i>P-genericity for Recurs
 ively Enumerable Sets.</i>\nUniversity of Illinois at Urbana-Champaign\, 1
 981.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR