The complexity of recursion theoretic games

Kummer, Martin

doi:10.1090/S0002-9947-05-04074-2

The complexity of recursion theoretic games
HTML articles powered by AMS MathViewer

by Martin Kummer PDF

Trans. Amer. Math. Soc. 358 (2006), 59-86 Request permission

Abstract:

We show that some natural games introduced by Lachlan in 1970 as a model of recursion theoretic constructions are undecidable, contrary to what was previously conjectured. Several consequences are pointed out; for instance, the set of all $\Pi _2$-sentences that are uniformly valid in the lattice of recursively enumerable sets is undecidable. Furthermore we show that these games are equivalent to natural subclasses of effectively presented Borel games.

References

Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B. G. Teubner, Leipzig, 1901.
Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning ways for your mathematical plays. Vol. 1, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1982. Games in general. MR 654501
Allan Borodin and Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, 1998. MR 1617778
J. Richard Büchi and Lawrence H. Landweber, Solving sequential conditions by finite-state strategies, Trans. Amer. Math. Soc. 138 (1969), 295–311. MR 280205, DOI 10.1090/S0002-9947-1969-0280205-0
James P. Carse. Finite and infinite games. Free Press, New York, 1986.
Douglas Cenzer and Jeffrey Remmel, Recursively presented games and strategies, Math. Social Sci. 24 (1992), no. 2-3, 117–139. MR 1189721, DOI 10.1016/0165-4896(92)90059-E
Morton Davis, Infinite games of perfect information, Advances in Game Theory, Princeton Univ. Press, Princeton, N.J., 1964, pp. 85–101. MR 0170727
Manfred Eigen, Ruthild Winkler. Das Spiel. Piper Verlag, Munich, 1975. English Translation: Laws of the game. Knopf, New York, 1981.
S. Even and R. E. Tarjan, A combinatorial problem which is complete in polynomial space, J. Assoc. Comput. Mach. 23 (1976), no. 4, 710–719. MR 436659, DOI 10.1145/321978.321989
Erich Grädel, Wolfgang Thomas, and Thomas Wilke (eds.), Automata, logics, and infinite games, Lecture Notes in Computer Science, vol. 2500, Springer-Verlag, Berlin, 2002. A guide to current research. MR 2070731, DOI 10.1007/3-540-36387-4
Yuri Gurevich. Infinite games. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 38 (1989), 93–100.
Wilfrid Hodges, Building models by games, London Mathematical Society Student Texts, vol. 2, Cambridge University Press, Cambridge, 1985. MR 812274
Johan Huizinga. Homo ludens: proeve eener bepaling van het spel-element der cultuur. H. D. Tjeenk Willink, Haarlem, 1938. English Translation: Homo ludens: a study of the play-element in our culture. Routledge & K. Paul, London, 1949.
Thomas John, Recursion in Kolmogorov’s $R$-operator and the ordinal $\sigma _3$, J. Symbolic Logic 51 (1986), no. 1, 1–11. MR 830066, DOI 10.2307/2273936
J. P. Jones, Some undecidable determined games, Internat. J. Game Theory 11 (1982), no. 2, 63–70. MR 686391, DOI 10.1007/BF01769063
Alexander S. Kechris, On Spector classes, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77) Lecture Notes in Math., vol. 689, Springer, Berlin, 1978, pp. 245–277. MR 526922
Bakhadyr Khoussainov and Anil Nerode, Automata theory and its applications, Progress in Computer Science and Applied Logic, vol. 21, Birkhäuser Boston, Inc., Boston, MA, 2001. MR 1839464, DOI 10.1007/978-1-4612-0171-7
Martin Kummer and Matthias Ott, Effective strategies for enumeration games, Computer science logic (Paderborn, 1995) Lecture Notes in Comput. Sci., vol. 1092, Springer, Berlin, 1996, pp. 368–387. MR 1461887, DOI 10.1007/3-540-61377-3_{4}9
A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 227009, DOI 10.1090/S0002-9947-1968-0227009-1
A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123–146. MR 227008
A. H. Lachlan, On some games which are relevant to the theory of recursively enumerable sets, Ann. of Math. (2) 91 (1970), 291–310. MR 284333, DOI 10.2307/1970579
Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718, DOI 10.1007/978-3-662-21755-9
Edouard Lucas. Récréations mathématiques. 4 Vols., Gauthier-Villars, Paris, 1881–1894.
Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 403976, DOI 10.2307/1971035
Donald A. Martin, $\Pi ^{1}_{2}$ monotone inductive definitions, Cabal Seminar 77–79 (Proc. Caltech-UCLA Logic Sem., 1977–79) Lecture Notes in Math., vol. 839, Springer, Berlin-New York, 1981, pp. 215–233. MR 611175
Donald A. Martin, Robert M. Solovay. Unpublished notes. 1975. Communicated by Alexander S. Kechris.
Yuri V. Matijacevič. Enumerable sets are diophantine. Dokl. Akad. Nauk. SSSR 191(2) (1970), 279–282. (in Russian)
John Maynard Smith. Evolution and the theory of games. Cambridge University Press, Cambridge, 1982.
Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
Sylvia Nasar, A beautiful mind, Simon & Schuster, New York, 1998. MR 1631630
John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, N.J., 1944. MR 0011937
Friedrich Nietzsche. Menschliches, Allzumenschliches; Zweiter Band. E. W. Fritzsch, Leipzig, 1886. English Translation by R. J. Hollingdale: Human, all too human. Cambridge University Press, Cambridge, 1986.
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
Michael O. Rabin, Effective computability of winning strategies, Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N.J., 1957, pp. 147–157. MR 0093740
Hugo Rahner. Der spielende Mensch. Johannes Verlag Einsiedeln, Freiburg, 1952. English Translation: Man at play. Burns & Oates, London, 1965.
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Thomas J. Schaefer, On the complexity of some two-person perfect-information games, J. Comput. System Sci. 16 (1978), no. 2, 185–225. MR 490917, DOI 10.1016/0022-0000(78)90045-4
Bernhard Schäfers (Editor). Grundbegriffe der Soziologie. 5th Edition, Leske + Budrich, Opladen, 1998.
Josef Seifert. Schachphilosophie. Wissenschaftliche Buchgesellschaft, Darmstadt, 1989.
Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
Ludwig Wittgenstein. Philosophische Untersuchungen. In: Schriften 1, Suhrkamp, Frankfurt am Main 1960. English Translation: Philosophical investigations. Blackwell, Oxford, 1953.