Game arguments in computability theory and algorithmic information theory

In S. Barry Cooper (ed.), How the World Computes. pp. 655--666 (2012)
  Copy   BIBTEX

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.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,590

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Abstract complexity theory and the Δ20 degrees.Benjamin Schaeffer - 2002 - Annals of Pure and Applied Logic 115 (1-3):195-231.
Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
The application of algorithmic information theory to noisy patterned strings.Sean Devine - 2006 - Complexity 12 (2):52-58.
Algorithmic randomness and measures of complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Turing’s algorithmic lens: From computability to complexity theory.Josep Díaz & Carme Torras - 2013 - Arbor 189 (764):a080.
Algorithmic Randomness and Complexity.Rodney G. Downey & Denis R. Hirschfeldt - 2010 - Springer.
Computability-theoretic complexity of countable structures.Valentina S. Harizanov - 2002 - Bulletin of Symbolic Logic 8 (4):457-477.
Algorithmic randomness and complexity. Theory and Applications of Computability.Rodney G. Downey & Denis R. Hirschfeldt - 2012 - Bulletin of Symbolic Logic 18 (1):126-128.
Effective fractal dimensions.Jack H. Lutz - 2005 - Mathematical Logic Quarterly 51 (1):62-72.
How to run algorithmic information theory on a computer:Studying the limits of mathematical reasoning.Gregory J. Chaitin - 1996 - Complexity 2 (1):15-21.

Analytics

Added to PP
2014-01-28

Downloads
32 (#127,447)

6 months
1 (#1,912,481)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references