Kolmogorov complexity and games
Nikolay Vereshchagin · 2008
In this survey we consider some results on Kolmogorov complexity whose proofs are based on interesting games. The close relation between Recursion theory, whose part is Kolmogorov complexity, and Game theory was revealed by Andrey Muchnik. In [10], he associated with every statement φ of Recursion theory a game Gφ that has the following properties. First, Gφ is a game with complete information between two players, Muchnik called them Nature and Mathematician; players make in turn infinitely many moves, every move is 0 or 1. Second, if Mathematician has a computable winning strategy in the game Gφ then φ is true. Third, if Nature has a computable winning strategy then φ is false. For all natural statements φ the winning condition in the game Gφ is defined by a Borel set (Mathematician wins if the sequence of moves made by the players belongs to a certain Borel subset of {0, 1}N); so we assume that this is the case. By Martin’s theorem [9] this assumption implies that Gφ is a determined game, that is, either Nature or Mathematician has a winning strategy. It might happen however that neither player has a computable winning strategy. In this case we cannot say anything about validity of φ. Muchnik’s general theorem applies to all statements on Kolmogorov complexity (with no time or space restrictions on description modes). Thus we can use Muchnik’s theorem to find out whether a statement φ on Kolmogorov complexity we are interested in is true or false. To this end, given φ we first find the game Gφ. Usually the game Gφ does not look very natural and ∗Supported by grant 06-01-00122 from RFBR. Paper written while visiting CWI, Amsterdam.