# MAMLS at Rutgers, October 6-7, 2012

The Fall 2012 MAMLS Meeting will take place at Rutgers University on October 6-7, 2012. The invited speakers include Clinton Conley, Andrew Marks, Antonio Montalban, Justin Moore, Saharon Shelah, Dima Sinapova and Anush Tserunyan.

The lectures will take place in Room 216 in Scott Hall on College Avenue Campus. For those of you who are coming by train, Scott Hall is a short walk from the train station.

For further information, visit:

http://www.math.rutgers.edu/~sthomas/RU2012.html

# The hierarchy of equivalence relations on $\mathbb{N}$ under computable reducibility, New York March 2012

I gave a talk at the CUNY MAMLS conference March 9-10, 2012 at the City University of New York.

This talk will be about a 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 the 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.

# Panel discussion on the unity and diversity of logic, New York, March 2012

As a part of the Spring 2012 Mid-Atlanatic Mathematical Logic Seminar, to be held March 9-10, 2012 at the CUNY Graduate Center, I shall participate in the following panel discussion.

Panel discussion: The unity and diversity of logic

Abstract.  The field of mathematical logic sometimes seems to be fracturing into ever-finer subdisciplines, with little connection between them, and many logicians now identify themselves by their specific subdiscipline.  On the other hand, certain new themes have appeared which tend to unify the diverse discoveries of the many subdisciplines.  This discussion will address these trends and ask whether one is likely to dominate the other in the long term.  Will logic remain a single field, or will it split into many unrelated branches?

The panelists will be Prof. Gregory Cherlin, myself, Prof. Rohit Parikh, and Prof. Jouko Väänänen, with the discussion moderated by Prof. Russell Miller. Questions and participation from the audience are encouraged.

As preparation for this panel discussion, please suggest points or topics that might brought up at the panel discussion, by posting suitable comments below.  Perhaps we’ll proceed with our own pre-discussion discussion here!

# 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.