Game arguments in computability theory and algorithmic information theory
classification
🧮 math.LO
cs.GTcs.ITmath.IT
keywords
theoryalgorithmicargumentscomplexitycomputabilityconditionalinformationsome
read the original 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
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.