Tag Archives: Cambridge

Forcing as a computational process, Cambridge, Februrary 2019

Posted on by
4

This will be a talk for Set Theory in the United Kingdom (STUK 1), to be held in the other place, February 16, 2019.

Abstract. We investigate the senses in which set-theoretic forcing can be seen as a computational process on the models of set theory. Given an oracle for the atomic or elementary diagram of a model of set theory $\langle M,\in^M\rangle$, for example, we explain senses in which one may compute $M$-generic filters $G\subset P\in M$ and the corresponding forcing extensions $M[G]$. Meanwhile, no such computational process is functorial, for there must always be isomorphic alternative presentations of the same model of set theory $M$ that lead by the computational process to non-isomorphic forcing extensions $M[G]\not\cong M[G’]$. Indeed, there is no Borel function providing generic filters that is functorial in this sense.

This is joint work with Russell Miller and Kameryn Williams.

The mate-in-n problem of infinite chess is decidable, Cambridge, June 2012

Posted on by
Reply

This will be a contributed talk at the Turing Centenary Conference CiE 2012 held June 18-23, 2012 in Cambridge, UK.

Abstract.  The mate-in-$n$ problem of infinite chess—chess played on an infinite edgeless board—is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. Although a straightforward formulation of this problem leads to assertions of high arithmetic complexity, with $2n$ alternating quantifiers,  the main theorem of this article nevertheless confirms a conjecture of the second author and C. D. A. Evans by establishing that it 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 $\frak{Ch}$, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. The structure is also definable in Presburger arithmetic. 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^{\rm chess}$ is not known.

Article | Slides | CiE 2012 | Contributed talk schedule

The hierarchy of equivalence relations on the natural numbers under computable reducibility, Cambridge, March 2012

Posted on by
Reply

This is a talk I shall give at the workshop on Logical Approaches to Barriers in Complexity II, March 26-30, 2012, a part of the program Semantics and Syntax: A Legacy of Alan Turing at the Isaac Newton Institute for Mathematical Sciences in Cambridge, where I am currently a Visiting Fellow.

Many of the naturally arising equivalence relations in mathematics, such as isomorphism relations on various types of countable structures, turn out to be equivalence relations on a standard Borel space, and these relations form an intensely studied hierarchy under Borel reducibility.  The topic of this talk is to introduce and explore the computable analogue of this robust theory, by studying the corresponding hierarchy of equivalence relations on the natural numbers under computable reducibility.  Specifically, one relation $E$ is computably reducible to another $F$ , if there is a unary computable function $f$ such that $x\mathrel{E}y$ if and only if $f(x)\mathrel{F}f(y)$.  This gives rise to a very different hierarchy than the Turing degrees on such relations, since it is connected with the difficulty of the corresponding classification problems, rather than with the difficulty of computing the relations themselves.  The theory is 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.  An abundance of open questions remain, and the subject is an attractive mix of methods from mathematical logic, computability, set theory, particularly descriptive set theory, and the rest of mathematics, subjects in which many of the equivalence relations arise.  This is joint work with Sam Coskey and Russell Miller.

Slides | Slides (longer version, from a similar talk) | Article | Conference abstract | Video

Infinite chess: the mate-in-n problem is decidable and the omega-one of chess, Cambridge, March 2012

Posted on by
Reply

I have just taken up a visiting fellow position at the Isaac Newton Institute for mathematical sciences in Cambridge, UK, where I am participating in the program Syntax and Semantics:  the legacy of Alan Turing.   I was asked to give a brief introduction to some of my current work, and I chose to speak about infinite chess.

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, in joint work with Dan Brumleve and Philipp Schlicht, confirming a conjecture of myself and C. D. A. Evans, we establish 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^{\rm chess}$ is not known.  I will also discuss recent joint work with C. D. A. Evans and W. Hugh Woodin showing that the omega one of infinite positions in three-dimensional infinite chess is true $\omega_1$: every countable ordinal is realized as the game value of such a position.

 

article | slides | streaming video | program of abstracts