Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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.
Similar Articles
Additional Information
  • Martin Kummer
  • Affiliation: INIT GmbH, Kaeppelestrasse 6, D-76131 Karlsruhe, Germany
  • Email: mkummer@init-ka.de
  • Received by editor(s): June 30, 2003
  • Published electronically: August 25, 2005
  • © Copyright 2005 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 358 (2006), 59-86
  • MSC (2000): Primary 03D25, 03D35, 03E15; Secondary 91A05, 91A46
  • DOI: https://doi.org/10.1090/S0002-9947-05-04074-2
  • MathSciNet review: 2171223