Abstract : We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional complexity and total conditional complexity, Epstein--Levin theorem and some (yet unpublished) result of Muchnik and Vyugin
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845799
Contributor : Andrei Romashchenko <>
Submitted on : Wednesday, August 21, 2013 - 12:15:25 PM Last modification on : Thursday, May 24, 2018 - 3:59:23 PM
Andrej Muchnik, Alexander Shen, Mikhail Vyugin. Game arguments in computability theory and algorithmic information theory. CiE: Computability in Europe, Jun 2012, Cambridge, United Kingdom. pp.655-666. ⟨lirmm-00845799⟩