Game arguments in computability theory and algorithmic information theory

DOI10.1007/978-3-642-30870-3_66MaRDI QIDQ2904462zbMATH OpenOpenAlexWikidataFDO

Authors A. Shen

Publication date 14 August 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.0198

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Theory of numerations, effectively presented structures (03D45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of game theory (91A80)

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

Recommendations

• Information, randomness and incompleteness. Papers on algorithmic information theory
• Algorithmic information theory
• scientific article; zbMATH DE number 4131660
• Expository notes on computability and complexity in (arithmetical) games
• A new version of algorithmic information theory.

Cited in

(9)

• Expository notes on computability and complexity in (arithmetical) games
• Short lists with short programs in short time
• Topological arguments for Kolmogorov complexity
• On approximate decidability of minimal programs
• Algorithmic minimal sufficient statistics: a new approach
• Algorithmic statistics: normal objects and universal models
• Branching time, perfect information games, and backward induction
• The Kolmogorov birthday paradox
• Total conditional complexity of certain objects

This page was built for publication: Game arguments in computability theory and algorithmic information theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904462)