Game arguments in computability theory and algorithmic information theory - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

Game arguments in computability theory and algorithmic information theory

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

Dates and versions

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

Identifiers

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

Cite

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⟩
138 View
0 Download

Altmetric

Share

Gmail Facebook X LinkedIn More