Transactions of the American Mathematical Society

Author(s): Martin Kummer
Journal: Trans. Amer. Math. Soc. 358 (2006), 59-86.
MSC (2000): Primary 03D25, 03D35, 03E15; Secondary 91A05, 91A46
Posted: August 25, 2005
Retrieve article in: PDF DVI PostScript

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.

1.: Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B. G. Teubner, Leipzig, 1901.
2.: Jon Barwise (Editor). Handbook of mathematical logic. North-Holland, Amsterdam, 1977. MR 0457132 (56:15351)
3.: Elwyn R. Berlekamp, John H. Conway, Richard K. Guy. Winning ways. 2 Vols., Academic Press, London, 1982. MR 0654502 (84h:90091b)
4.: Allan Borodin, Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, Cambridge, 1998. MR 1617778 (2000g:68053)
5.: J. Richard Büchi, Lawrence H. Landweber. Solving sequential conditions by finite-state strategies. Trans. Amer. Math. Soc. 138 (1969), 295-311. MR 0280205 (43:5926)
6.: James P. Carse. Finite and infinite games. Free Press, New York, 1986.
7.: Douglas A. Cenzer, Jeffrey B. Remmel. Recursively presented games and strategies. Math. Social Sci. 24 (1992), 117-139. MR 1189721 (93m:03078)
8.: Morton D. Davis. Infinite games of perfect information. Ann. of Math. Stud., vol. 52, 1964, pp. 85-101. MR 0170727 (30:965)
9.: Manfred Eigen, Ruthild Winkler. Das Spiel. Piper Verlag, Munich, 1975. English Translation: Laws of the game. Knopf, New York, 1981.
10.: Shimon Even, Robert E. Tarjan. A combinatorial problem which is complete for polynomial space. J. ACM 23 (1976), 710-719. MR 0436659 (55:9600)
11.: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Editors). Automata, logics, and infinite games. Lecture Notes in Computer Science, vol. 2500, Springer-Verlag, Berlin, 2002. MR 2070731 (2005b:68009)
12.: Yuri Gurevich. Infinite games. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 38 (1989), 93-100.
13.: Wilfred Hodges. Building models by games. Cambridge University Press, Cambridge, 1985. MR 0812274 (87h:03045)
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 $\sigma_3$ . J. Symbolic Logic 51 (1986), 1-11. MR 0830066 (87i:03094)
16.: James P. Jones. Some undecidable determined games. Internat. J. Game Theory 11(2) (1982), 63-70. MR 0686391 (84b:90107)
17.: Alexander S. Kechris. On Spector classes. Cabal Seminar 76-77. Lecture Notes in Mathematics vol. 689, Springer-Verlag, Berlin, 1978, pp. 245-277. MR 0526922 (81b:03053)
18.: Bakhadyr Khoussainov, Anil Nerode. Automata theory and its applications. Birkhäuser, Boston, 2001. MR 1839464 (2004e:03073)
19.: Martin Kummer, Matthias Ott. Effective strategies for enumeration games. Interner Bericht 1995, 41. Fakultät für Informatik, Universität Karlsruhe, 1995. Available from: URL: http://www.ubka.uni-karlsruhe.de/cgi-bin/psview?document=ira/1995/41. Also published in: Computer Science Logic, CSL'95, Lecture Notes in Computer Science, vol. 1092, Springer-Verlag, Berlin, 1996, pp. 368-387. MR 1461887 (98c:03026)
20.: Alistair H. Lachlan. On the lattice of recursively enumerable sets. Trans. Amer. Math. Soc. 130 (1968), 1-37. MR 0227009 (37:2594)
21.: Alistair H. Lachlan. The elementary theory of recursively enumerable sets. Duke Math. J. 35 (1968), 123-146. MR 0227008 (37:2593)
22.: Alistair H. Lachlan. On some games which are relevant to the theory of recursively enumerable sets. Ann. of Math. 91(2) (1970), 291-310. MR 0284333 (44:1562)
23.: Manuel Lerman. Degrees of unsolvability. Springer-Verlag, Berlin, 1983. MR 0708718 (85h:03044)
24.: Edouard Lucas. Récréations mathématiques. 4 Vols., Gauthier-Villars, Paris, 1881-1894.
25.: Donald A. Martin. Borel determinacy. Ann. of Math. 102(2) (1975), 363-371. MR 0403976 (53:7785)
26.: Donald A. Martin. $\Pi^1_2$ monotone inductive definitions. Cabal Seminar 77-79. Lecture Notes in Mathematics, vol. 839, Springer-Verlag, Berlin, 1981, pp. 215-233. MR 0611175 (83g:03047)
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. North-Holland, Amsterdam, 1980. MR 0561709 (82e:03002)
31.: Sylvia Nasar. A beautiful mind. Simon & Schuster, New York, 1998. MR 1631630 (99j:01021)
32.: John von Neumann, Oskar Morgenstern. Theory of games and economic behavior. Princeton University Press, Princeton, 1944. MR 0011937 (6:235k)
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, Reading, 1994. MR 1251285 (95f:68082)
35.: Michael O. Rabin. Effective computability of winning strategies. Ann. of Math. Stud., vol. 39, 1957, pp. 147-157. MR 0093740 (20:263)
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, New York, 1967. MR 0224462 (37:61)
38.: Thomas J. Schaefer. On the complexity of some two-person perfect-information games. J. Comput. and System Sci. 16 (1978), 185-225. MR 0490917 (80e:90131)
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. Springer-Verlag, Berlin, 1987. MR 0882921 (88m:03003)
42.: Ludwig Wittgenstein. Philosophische Untersuchungen. In: Schriften 1, Suhrkamp, Frankfurt am Main 1960. English Translation: Philosophical investigations. Blackwell, Oxford, 1953.

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

Martin Kummer
Affiliation: INIT GmbH, Kaeppelestrasse 6, D-76131 Karlsruhe, Germany
Email: mkummer@init-ka.de

DOI: 10.1090/S0002-9947-05-04074-2
PII: S 0002-9947(05)04074-2
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
Posted: August 25, 2005
Dedicated: 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
Copyright of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS