The mate-in-n problem of infinite chess is decidable

  • D. Brumleve, J. D. Hamkins, and P. Schlicht, “The Mate-in-$n$ Problem of Infinite Chess Is Decidable,” in How the World Computes, S. Cooper, A. Dawar, and B. Löwe, Eds., Springer, 2012, vol. 7318, pp. 78-88.  
    @incollection{BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable,
    year= {2012},
    isbn= {978-3-642-30869-7},
    booktitle= {How the World Computes},
    volume= {7318},
    series= {Lecture Notes in Computer Science},
    editor= {Cooper, S.~Barry and Dawar, Anuj and Löwe, Benedikt},
    doi= {10.1007/978-3-642-30870-3_9},
    title= {The Mate-in-$n$ Problem of Infinite Chess Is Decidable},
    url= {http://wp.me/p5M0LV-f8},
    publisher= {Springer},
    author= {Brumleve, Dan and Hamkins, Joel David and Schlicht, Philipp},
    pages= {78-88},
    eprint = {1201.5597},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\frak{Ch}}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?

The hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility, Florida, 2012

This is a talk at the Alan Turing centenary conference at Florida Atlantic University, January 13-15, 2012, sponsored by MAMLS, and part of the 2012 Alan Turing Year of events in celebration of the one hundredth year of the birth of Alan Turing.

This talk will be about a recent generalization of the concept of Turing degrees to the hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility.  The idea is to develop a computable analogue of the enormously successful theory of equivalence relations on $\mathbb{R}$ under Borel reducibility, a theory which has led to deep insights on the complexity hierarchy of classification problems arising throughout mathematics. In our computable analogue, we consider the corresponding reduction notion in the context of Turing computability for relations on $\mathbb{N}$.  Specifically, one relation $E$ is computably reducible to another, $F$, if there is a computable function $f$ such that $x\mathrel{E} y$ if and only if $f(x)\mathrel{F} f(y)$.  This is a very different concept from mere Turing reducibility of $E$ to $F$, for it sheds light on the comparative difficulty of the classification problems corresponding to $E$ and $F$, rather than on the difficulty of computing the relations themselves.  In particular, the theory appears well suited for an analysis of equivalence relations on classes of c.e. structures, a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. In this regard, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remain.  This is joint work with Sam Coskey and Russell Miller.

Article | Sam’s post on this topic | Slides

The halting problem is decidable on a set of asymptotic probability one

  • J. D. Hamkins and A. Miasnikov, “The halting problem is decidable on a set of asymptotic probability one,” Notre Dame J.~Formal Logic, vol. 47, iss. 4, pp. 515-524, 2006.  
    @ARTICLE{HamkinsMiasnikov2006:HaltingProblemDecidable,
    AUTHOR = {Hamkins, Joel David and Miasnikov, Alexei},
    TITLE = {The halting problem is decidable on a set of asymptotic probability one},
    JOURNAL = {Notre Dame J.~Formal Logic},
    FJOURNAL = {Notre Dame Journal of Formal Logic},
    VOLUME = {47},
    YEAR = {2006},
    NUMBER = {4},
    PAGES = {515--524},
    ISSN = {0029-4527},
    CODEN = {NDJFAM},
    MRCLASS = {03D10 (68Q05)},
    MRNUMBER = {2272085 (2007m:03082)},
    MRREVIEWER = {Maurice Margenstern},
    DOI = {10.1305/ndjfl/1168352664},
    URL = {http://jdh.hamkins.org/haltingproblemdecidable/},
    eprint = {math/0504351},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    file = F,
    }

The halting problem for Turing machines is decidable on a set of asymptotic probability one. Specifically, there is a set B of Turing machine programs such that (i) B has asymptotic probability one, so that as the number of states n increases, the proportion of all n-state programs that are in B goes to one; (ii) B is polynomial time decidable; and (iii) the halting problem H intersect B is polynomial time decidable. The proof is sensitive to the particular computational model.