Game arguments in computability theory and algorithmic information theory

Andrej Muchnik 1 Alexander Shen 2 Mikhail Vyugin 1
1 INT - Institute of New Technologies in Education
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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
Document type :
Conference papers
Complete list of metadatas
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

Links full text

arxiv

Identifiers

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

Collections

CNRS | INSMI | ESCAPE | LIRMM | MIPS | UNIV-MONTPELLIER

Citation

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

225

Contact

Informations

CCSD