Game arguments in computability theory and algorithmic information theory

Andrej Muchnik 1 Alexander Shen 2 Mikhail Vyugin 1
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
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

Identifiants

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

Collections

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〉

Partager

Métriques

Consultations de la notice

154