Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)


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: http://dx.doi.org/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
Published electronically: August 25, 2005
Dedicated: \begin{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 \end{quotation}
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.