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
Type de document :
Communication dans un congrès
CiE: Computability in Europe, Jun 2012, Cambridge, United Kingdom. pp.655-666, 2012, 〈http://www.mathcomp.leeds.ac.uk/turing2012/WScie12/give-page.php?8〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845799
Contributeur : Andrei Romashchenko <>
Soumis le : mercredi 21 août 2013 - 12:15:25
Dernière modification le : jeudi 11 janvier 2018 - 06:27:05

Lien texte intégral

arxiv

Identifiants

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

Collections

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, 2012, 〈http://www.mathcomp.leeds.ac.uk/turing2012/WScie12/give-page.php?8〉. 〈lirmm-00845799〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

165

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD