The complexity of recursion theoretic games. (English) Zbl 1079.03029
Summary: 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.
MSC:
| 03D25 | Recursively (computably) enumerable sets and degrees |
| 03D35 | Undecidability and degrees of sets of sentences |
| 03E15 | Descriptive set theory |
| 91A05 | 2-person games |
| 91A46 | Combinatorial games |
Keywords:
undecidability; uniformity; analytical hierarchy; effective descriptive set theory; recursively enumerable sets; Borel gamesReferences:
| [1] | Wilhelm Ahrens. Mathematische Unterhaltungen und Spiele. B. G. Teubner, Leipzig, 1901. · JFM 31.0220.02 |
| [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. |
| [3] | 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. 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. · Zbl 0485.00025 |
| [4] | Allan Borodin and Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, 1998. · Zbl 0931.68015 |
| [5] | J. Richard Büchi and Lawrence H. Landweber, Solving sequential conditions by finite-state strategies, Trans. Amer. Math. Soc. 138 (1969), 295 – 311. · Zbl 0182.02302 |
| [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. · Zbl 0786.90103 · doi: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. · Zbl 0133.13104 |
| [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. · Zbl 0355.68041 · doi:10.1145/321978.321989 |
| [11] | Erich Grädel, Wolfgang Thomas, and Thomas Wilke , Automata, logics, and infinite games, Lecture Notes in Computer Science, vol. 2500, Springer-Verlag, Berlin, 2002. A guide to current research. · Zbl 1011.00037 |
| [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. · Zbl 0569.03015 |
| [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 \?\(_{3}\), J. Symbolic Logic 51 (1986), no. 1, 1 – 11. · Zbl 0648.03033 · doi:10.2307/2273936 |
| [16] | J. P. Jones, Some undecidable determined games, Internat. J. Game Theory 11 (1982), no. 2, 63 – 70. · Zbl 0498.90090 · doi: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. · Zbl 0405.03022 |
| [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. · Zbl 1083.68058 |
| [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. · doi: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. · Zbl 0281.02042 |
| [21] | A. H. Lachlan, The elementary theory of recursively enumerable sets, Duke Math. J. 35 (1968), 123 – 146. · Zbl 0281.02043 |
| [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. · Zbl 0276.02023 · doi:10.2307/1970579 |
| [23] | Manuel Lerman, Degrees of unsolvability, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. · Zbl 0542.03023 |
| [24] | Edouard Lucas. Récréations mathématiques. 4 Vols., Gauthier-Villars, Paris, 1881-1894. · Zbl 0088.00101 |
| [25] | Donald A. Martin, Borel determinacy, Ann. of Math. (2) 102 (1975), no. 2, 363 – 371. · Zbl 0336.02049 · doi:10.2307/1971035 |
| [26] | Donald A. Martin, \Pi \textonesuperior \(_{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. |
| [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. · Zbl 0526.90102 |
| [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. · Zbl 0433.03025 |
| [31] | Sylvia Nasar, A beautiful mind, Simon & Schuster, New York, 1998. · Zbl 0907.01038 |
| [32] | John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior, Princeton University Press, Princeton, New Jersey, 1944. · Zbl 0063.05930 |
| [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. · Zbl 0833.68049 |
| [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. · Zbl 0078.32902 |
| [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. |
| [38] | Thomas J. Schaefer, On the complexity of some two-person perfect-information games, J. Comput. System Sci. 16 (1978), no. 2, 185 – 225. · Zbl 0383.90112 · doi: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. · Zbl 0667.03030 |
| [42] | Ludwig Wittgenstein. Philosophische Untersuchungen. In: Schriften 1, Suhrkamp, Frankfurt am Main 1960. English Translation: Philosophical investigations. Blackwell, Oxford, 1953. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
