Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The complexity of recursion theoretic games

Author: Martin Kummer
Journal: Trans. Amer. Math. Soc. 358 (2006), 59-86
MSC (2000): Primary 03D25, 03D35, 03E15; Secondary 91A05, 91A46
Published electronically: August 25, 2005
MathSciNet review: 2171223
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B. G. Teubner, Leipzig, 1901.
  • 2. Handbook of mathematical logic, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. Edited by Jon Barwise; With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra; Studies in Logic and the Foundations of Mathematics, Vol. 90. MR 0457132
  • 3. Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning ways for your mathematical plays. Vol. 2, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1982. Games in particular. MR 654502
  • 4. Allan Borodin and Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, 1998. MR 1617778
  • 5. J. Richard Büchi and Lawrence H. Landweber, Solving sequential conditions by finite-state strategies, Trans. Amer. Math. Soc. 138 (1969), 295–311. MR 0280205, 10.1090/S0002-9947-1969-0280205-0
  • 6. James P. Carse. Finite and infinite games. Free Press, New York, 1986.
  • 7. Douglas Cenzer and Jeffrey Remmel, Recursively presented games and strategies, Math. Social Sci. 24 (1992), no. 2-3, 117–139. MR 1189721, 10.1016/0165-4896(92)90059-E
  • 8. Morton Davis, Infinite games of perfect information, Advances in game theory, Princeton Univ. Press, Princeton, N.J., 1964, pp. 85–101. MR 0170727
  • 9. Manfred Eigen, Ruthild Winkler. Das Spiel. Piper Verlag, Munich, 1975. English Translation: Laws of the game. Knopf, New York, 1981.
  • 10. 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 0436659
  • 11. 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
  • 12. Yuri Gurevich. Infinite games. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 38 (1989), 93-100.
  • 13. Wilfrid Hodges, Building models by games, London Mathematical Society Student Texts, vol. 2, Cambridge University Press, Cambridge, 1985. MR 812274
  • 14. 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.
  • 15. Thomas John, Recursion in Kolmogorov’s 𝑅-operator and the ordinal 𝜎₃, J. Symbolic Logic 51 (1986), no. 1, 1–11. MR 830066, 10.2307/2273936
  • 16. J. P. Jones, Some undecidable determined games, Internat. J. Game Theory 11 (1982), no. 2, 63–70. MR 686391, 10.1007/BF01769063
  • 17. 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
  • 18. 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
  • 19. 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, 10.1007/3-540-61377-3_49
  • 20. A. H. Lachlan, On the lattice of recursively enumerable sets, Trans. Amer. Math. Soc. 130 (1968), 1–37. MR 0227009, 10.1090/S0002-9947-1968-0227009-1
  • 21. A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123–146. MR 0227008
  • 22. 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 0284333
  • 23. Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR 708718
  • 24. Edouard Lucas. Récréations mathématiques. 4 Vols., Gauthier-Villars, Paris, 1881-1894.
  • 25. Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363–371. MR 0403976
  • 26. Donald A. Martin, Π¹₂ 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
  • 27. Donald A. Martin, Robert M. Solovay. Unpublished notes. 1975. Communicated by Alexander S. Kechris.
  • 28. Yuri V. Matijacevic. Enumerable sets are diophantine. Dokl. Akad. Nauk. SSSR 191(2) (1970), 279-282. (in Russian)
  • 29. John Maynard Smith. Evolution and the theory of games. Cambridge University Press, Cambridge, 1982.
  • 30. 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
  • 31. Sylvia Nasar, A beautiful mind, Simon & Schuster, New York, 1998. MR 1631630
  • 32. John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey, 1944. MR 0011937
  • 33. 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.
  • 34. Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
  • 35. 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
  • 36. Hugo Rahner. Der spielende Mensch. Johannes Verlag Einsiedeln, Freiburg, 1952. English Translation: Man at play. Burns & Oates, London, 1965.
  • 37. Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
  • 38. 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, 10.1016/0022-0000(78)90045-4
  • 39. Bernhard Schäfers (Editor). Grundbegriffe der Soziologie. 5th Edition, Leske + Budrich, Opladen, 1998.
  • 40. Josef Seifert. Schachphilosophie. Wissenschaftliche Buchgesellschaft, Darmstadt, 1989.
  • 41. 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
  • 42. Ludwig Wittgenstein. Philosophische Untersuchungen. In: Schriften 1, Suhrkamp, Frankfurt am Main 1960. English Translation: Philosophical investigations. Blackwell, Oxford, 1953.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D25, 03D35, 03E15, 91A05, 91A46

Retrieve articles in all journals with MSC (2000): 03D25, 03D35, 03E15, 91A05, 91A46

Additional Information

Martin Kummer
Affiliation: INIT GmbH, Kaeppelestrasse 6, D-76131 Karlsruhe, Germany

Keywords: Undecidability, games, recursively enumerable sets, uniformity, lattice of recursively enumerable sets, analytical hierarchy, effective descriptive set theory, Borel games
Received by editor(s): June 30, 2003
Published electronically: August 25, 2005
Dedicated: \quotation Wir meinen, das Märchen und das Spiel gehöre zur Kindheit: wir Kurzsichtigen! Als ob wir in irgendeinem Lebensalter ohne Märchen und Spiel leben möchten! Friedrich Nietzsche \endquotation
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.