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
DOI: https://doi.org/10.1090/S0002-9947-05-04074-2
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?)


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
Email: mkummer@init-ka.de

DOI: https://doi.org/10.1090/S0002-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
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.