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://dx.doi.org/10.1305/ndjfl/1168352664},
    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.