Game arguments in computability theory and algorithmic information theory - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2012

Game arguments in computability theory and algorithmic information theory

Résumé

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

Dates et versions

lirmm-00845799 , version 1 (21-08-2013)

Identifiants

  • HAL Id : lirmm-00845799 , version 1
  • ARXIV : 1204.0198

Citer

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⟩
143 Consultations
0 Téléchargements

Altmetric

Partager

More