I study computability theory, the branch of mathematical logic concerned
with finite algorithms and the mathematical problems which such algorithms
can or cannot solve. By relativizing, one forms a partial order of the
degrees of difficulty (the *Turing degrees*) of such problems.
Computable model theory, my specialty, applies such techniques to general
mathematical structures such as fields, trees,
linear orders, groups and graphs. At present my investigations
focus particularly on fields, and on the possibility
of extending results from them to differential fields.

Traditional computable model theory only considers countable structures, but I am currently examining different ways of extending the notions of computable model theory to certain uncountable structures, either by examining the structures locally rather than globally, or by extending the notion of computability to ordinal time to allow computation of functions with larger domains, or by allowing the standard operations on real numbers to be taken as computable.

These papers are copyrighted and may be downloaded and/or printed only for personal or non-profit educational use.

**The $\Delta^0_2$-spectrum of a
linear order,**
*Journal of Symbolic Logic* **66** (2001), 470-486.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:Slaman and Wehner have constructed structures which distinguish the computable Turing degree0from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Delta^0_2 degree, but not0. Since our argument requires the technique of permitting below a Delta^0_2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting.

**Definable incompleteness and Friedberg splittings,** *Journal of
Symbolic Logic*, **67** (2002), 679-696.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We define a property R(A_0, A_1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A_0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A_0 and A_1 which we build satisfying R form a Friedberg splitting of their union A, with A_1 prompt and A promptly simple. We conclude that A_0 and A_1 lie in distinct orbits under automorphisms of E, yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit.

**Orbits of computably enumerable sets:
low sets can avoid an upper cone**, *Annals of
Pure and Applied Logic* **118** (2002),
61-85.
(Copyright held by Elsevier.)
pdf download

Abstract:We investigate the orbit of a low computably enumerable set under automorphisms of the partial order E of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of E mapping A to a set B such that C is not Turing-computable from B. Thus, the orbit in E of the low set A cannot be contained in the upper cone above C. This complements a result of Harrington, who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set.

**The computable dimension of I-trees of infinite
height** (with N. Kogabaev and O. Kudinov), *Algebra and
Logic* **43** (2004) 6, 393-407.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:An I-tree is a tree with a distinguished initial subtree defined by a unary relation I. We prove that no computable I-tree of height omega is computably categorical. Indeed, all such trees have computable dimension omega and moreover, their computable dimension is effectively infinite.

**The $\forall\exists$-theory of $\mathcal{R}(\leq, \wedge, \vee)$
is undecidable** (with A. Nies and R. Shore),
*Transactions of the American Mathematical Society*
**356** (2004) 8, 3025-3067.
(Copyright held by the American Mathematical Society.)
pdf download

Abstract:The three-quantifier theory of (R,\leq_{T}), the recursively enumerable degrees under Turing reducibility, was proven undecidable by Lempp, Nies and Slaman [1998]. The two-quantifier theory includes the lattice embedding problem and its decidability is a longstanding open question. A negative solution to this problem seems out of reach of the standard methods of interpretation of theories because the language is relational. We prove the undecidability of a fragment of the theory of R that lies between the two and three quantifier theories with \leq_{T} but includes function symbols.

**Computable categoricity for trees of finite height**
(with S. Lempp, C. McCoy, and R. Solomon), *Journal of
Symbolic Logic*, **70** (2005), 151-215.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Sigma^0_3-condition. We show that all trees which are not computably categorical have computable dimension omega. Finally, we prove that for every n > 0 in omega, there exists a computable tree of finite height which is Delta^{0}_{n+1}-categorical but not Delta^{0}_{n}-categorical.

**The computable dimension of trees of infinite
height**, *Journal of
Symbolic Logic*, **70** (2005), 111-141.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We prove that no computable tree of height omega is computably categorical, and indeed that all such trees have computable dimension omega.

**Enumerations in computable structure theory**
(with S. Goncharov, V. Harizanov, J. Knight, C. McCoy,
and R. Solomon), *Annals of Pure and Applied Logic*
**136** (2005) 3, 219-246.
(Copyright held by Elsevier.)
pdf download.

Abstract:We exploit properties of certain directed graphs, obtained from families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal alpha, we transform a countable directed graph G into a structure G* such that G has a Delta^0_alpha isomorphic copy if and only if G* has a computable isomorphic copy.

**Order-computable sets**
(with D. Hirschfeldt and S. Podzorov),
*The Notre Dame Journal of Formal Logic* **48** (2007) 3, 317-347.
(Copyright held by the University of Notre Dame.)
pdf download

Abstract:We give a straightforward computable-model-theoretic definition of a property of Delta^0_2 sets, called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

**Spectra of structures and relations**
(with V. Harizanov), * Journal of Symbolic
Logic* **72** (2007) 1, 324-348.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We consider embeddings of structures which preserve spectra: if g maps M into S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to bespectrally universal. We use our results to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on G. Finally, we consider the extent to which all spectra of unary relations on the structure L may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degreescsuch thatc'computes0''.

**An introduction to infinite time computable model theory**
(with J. Hamkins, D. Seabold, and S. Warner),
in the book
*New Computational Paradigms:
Changing Conceptions of What is Computable*,
eds. S.B. Cooper, B. Lowe, & A. Sorbi,
(New York: Springer-Verlag, 2007), 521-557.
pdf download

Abstract:We introduce infinite time computable model theory, the computable model theory arising with infinite time Turing machines, which provide infinitary notions of computability for structures built on the reals. Much of the finite time theory generalizes to the infinite time context, but several fundamental questions, including the infinite time computable analogue of the Completeness Theorem, turn out to be independent of ZFC.

**Locally computable structures**, in
*Computation and Logic
in the Real World - Third Conference on
Computability in Europe, CiE 2007*,
eds. B. Cooper, B. Lowe, & A. Sorbi,
*Lecture Notes in Computer Science 4497*
(Berlin: Springer-Verlag, 2007), 575-584.
(Copyright held by Springer-Verlag.)
pdf download
(includes an appendix omitted from the proceedings volume).

Abstract:We introduce the notion of alocally computable structure, a natural way of generalizing the notions of computable model theory to uncountable structures S by presenting the finitely generated substructures of S effectively. Our discussion emphasizes definitions and examples, but does prove two significant results. First, our notion of m-extensional local computability of S ensures that the Sigma_n-theory of S will be Sigma_n for all n up to m, even over parameters from S. Second, our notion of perfect local computability is equivalent (for countable structures) to the classic definition of computable presentability.

**The complexity of quickly ORM-decidable sets**
(with J. Hamkins & D. Linetsky), in
*Computation and Logic
in the Real World - Third Conference on
Computability in Europe, CiE 2007*,
eds. B. Cooper, B. Lowe, & A. Sorbi,
*Lecture Notes in Computer Science 4497*
(Berlin: Springer-Verlag, 2007), 488-496.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than omega^omega. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than omega_1^{CK}.

**Post's Problem for ordinal register machines**
(with J. Hamkins), in
*Computation and Logic
in the Real World - Third Conference on
Computability in Europe, CiE 2007*,
eds. B. Cooper, B. Lowe, & A. Sorbi,
*Lecture Notes in Computer Science 4497*
(Berlin: Springer-Verlag, 2007), 358-367.
(Copyright held by Springer-Verlag.)
See also the extension of this article immediately below.
pdf download

Abstract:We study Post's Problem for the ordinal register machines defined by Koepke and Siders, showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors results of Hamkins and Lewis for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time.

**Post's Problem for ordinal register machines:
an explicit approach**
(with J. Hamkins),
*Annals of Pure and Applied Logic*
**160** (2009) 3, 302-309.
This article is an extension of the one immediately above.
pdf download

Abstract:We study Post's Problem for the ordinal register machines defined by Koepke and Siders, showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors results of Hamkins and Lewis for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time. Additionally, we prove that there is a finite-time program which converts any ordinal-time register machine program to an ordinal-time Turing machine program, and another finite-time program which converts in the opposite direction, such that in each case the two programs compute the same partial function from ordinals to ordinals.

**Perfect local computability and computable simulations**
(with D. Mulcahey), in
*Logic and Theory of Algorithms - Fourth Conference on
Computability in Europe, CiE 2008*,
eds. A. Beckmann, C. Dimitracopoulos, & B. Lowe,
*Lecture Notes in Computer Science 5028*
(Berlin: Springer-Verlag, 2008), 388-397.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:We study perfectly locally computable structures, which are (possibly uncountable) structures S that have highly effective presentations of their local properties. We show that every such S can be simulated, in a strong sense and even over arbitrary finite parameter sets, by a computable structure. We also study the category theory of a perfect cover of S, examining its connections to the category of all finitely generated substructures of S.

**An enhanced theory of infinite time register machines**
(with P. Koepke), in
*Logic and Theory of Algorithms - Fourth Conference on
Computability in Europe, CiE 2008*,
eds. A. Beckmann, C. Dimitracopoulos, & B. Lowe,
*Lecture Notes in Computer Science 5028*
(Berlin: Springer-Verlag, 2008), 265-274.
See also the extension of this article immediately below.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Infinite time register machines(ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times a register content is defined as a liminf of previous register contents, if that limit is finite; otherwise the register is reset to 0. (A previous weaker version of infinitary register machines would halt without a result in case of such an overflow.) The theory of infinite time register machines has similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. Indeed ITRMs can decide all Pi^1_1 sets, yet they are strictly weaker than ITTMs.

**The basic theory of infinite time register machines**
(with M. Carl, T. Fischbach, P. Koepke, M. Nasfi, and G. Weckbecker),
*Archive for Mathematical Logic*
**49** (2010) 2, 249-273.
This article is an extension of the one immediately above.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Infinite time register machines(ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper we examine the ITRMs introduced by the third and fourth author, where a register content at a limit time is set to the liminf of previous register contents if that limit is finite; otherwise the register is reset to0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all Pi-1-1 sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion ofITRM-clockable ordinalscorresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a realrsuch that there is a programPthat halts on the empty input for all oracle contents and outputs1iff the oracle number isr, but no program can decide for every natural numbernwhether or notnlies inrwith the empty oracle.

**Is it harder to factor a polynomial
or to find a root?**,
*Transactions of the American Mathematical Society*
**362** (2010) 10, 5261-5281.
(Copyright held by the American Mathematical Society.)
pdf download

Abstract:For a computable field F, thesplitting setS is the set of polynomials p(X) in F[X] which factor over F, and theroot setR is the set of polynomials with roots in F. Work by Frohlich and Shepherdson essentially showed these two sets to be Turing-equivalent, surprising many mathematicians, since it is not obvious how to compute S from R. We apply other standard reducibilities from computability theory, along with a healthy dose of Galois theory, to compare the complexity of these two sets. We show, in contrast to the Turing equivalence, that for algebraic fields the root set has slightly higher complexity: both are computably enumerable, and computable algebraic fields always have S 1-reducible to R, but it is possible to make R not m-reducible to S. So the root set may be viewed as being more difficult than the splitting set to compute.

**d-Computable categoricity for algebraic fields**,
*Journal of Symbolic Logic*
**74** (2009) 4, 1325-1351.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields ared-computably categorical for a particular Turing degreedwithd'=0'', but that not all such fields are0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over the rationals.

**Spectra of algebraic fields and subfields**
(with A. Frolov and I. Kalimullin), in
*Mathematical Theory and Computational Practice -- Fifth Conference
on Computability in Europe, CiE 2009*,
eds. K. Ambos-Spies, B. Loewe, & W. Merkle,
*Lecture Notes in Computer Science 5635*
(Berlin: Springer-Verlag, 2009), 232-241.
(Copyright held by Springer-Verlag.)
pdf download
(includes an appendix omitted from the proceedings volume)

Abstract:An algebraic field extensionFofQorZ/(p)may be regarded either as a structure in its own right, or as a subfield of its algebraic closureE. We consider the Turing degree spectrum ofFin both cases, as a structure and as a relation onE, and characterize the sets of Turing degrees that are realized as such spectra. The results show a connection between enumerability in the structureFand computability whenFis seen as a subfield ofE.

**Real computable manifolds and homotopy groups**
(with W. Calvert),
*Unconventional Computation,
8th International Conference, UC 2009, Proceedings*,
eds. C. Calude, J. Costa, N. Dershowitz, E. Freire, & G. Rozenberg,
*Lecture Notes in Computer Science*
**5715**
(Berlin: Springer-Verlag, 2009), 98-109.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Using the model of real computability developed by Blum, Cucker, Shub, and Smale, we investigate the difficulty of determining the answers to several basic topological questions about manifolds. We state definitions of real-computable manifold and of real-computable paths in such manifolds, and show that, while BSS machines cannot in general decide such questions as nullhomotopy and simple connectedness for such structures, there are nevertheless real-computable presentations of paths and homotopy equivalence classes under which such computations are possible.

**Degrees of categoricity of computable structures**
(with E. Fokina and I. Kalimullin),
*Archive for Mathematical Logic*
**49** (2010) 1, 51-67.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Defining the degree of categoricity of a computable structureMto be the least degreedfor whichMisd-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for alln, degrees d.c.e. in and above0^(n)can be so realized, as can the degree0^(omega).

**Simple structures with complex symmetry,**
(with V. Harizanov and A. Morozov),
*Algebra and Logic*
**49** (2010) 1, 68-90.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:We define theautomorphism spectrumof a computable structureM, a measurement of the complexity of the symmetries ofM, and prove that certain sets of Turing degrees can be realized as automorphism spectra, while certain others cannot.

**Degree spectra of high-n and nonlow-n degrees**
(with A. Frolov, V. Harizanov, I. Kalimullin, and O. Kudinov),
*Journal of Logic and Computation*
**22** (2012) 4, 755-777.
(Copyright held by Oxford University Press.)
Preprint available for pdf download.

Abstract:We survey known results on spectra of structures and on spectra of relations on computable structures. asking when the set of all high-ndegrees can be such a spectrum, and likewise for the set of nonlow-ndegrees. We then repeat these questions specifically for linear orders and for relations on the computable dense linear orderQ. New results include realizations of the set of nonlow-nTuring degrees as the spectrum of a relation onQfor alln> 0, and a realization of the set of nonlow-nTuring degrees as the spectrum of a linear order whenevern> 1. The state of current knowledge is summarized in a table in the concluding section.

**Computability of Fraïssé limits**
(with B. Csima, V. Harizanov, and A. Montalbán),
*Journal of Symbolic Logic* **76** (2011) 1, 66-93.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:Fraïssé studied countable structures S through analysis of theageof S, i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on theFraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal.

**An introduction to computable model theory
on groups and fields,**
*Groups, Complexity, and Cryptology*
**3** (2011) 1.
(Copyright held by Walter de Gruyter GmbH und Co. KG.)
pdf download

Abstract:We introduce the standard computable-model-theoretic concepts of a computable group and a computable field, and use them to illustrate the sorts of questions about groups and fields which computability theorists investigate. This article is intended for group theorists with some background in algorithmic questions, such as the undecidability of the word problem and the conjugacy problem for finitely presented groups.

**Low-5 Boolean subalgebras and computable copies**,
*Journal of Symbolic Logic* **76** (2011) 3, 1061--1074.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:It is known that the spectrum of a Boolean algebra cannot contain a low-4 degree unless it also contains the degree0; it remains open whether the same holds for low-5 degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebraB. For such subalgebrasA, we show that it is possible for the spectrum of the unary relationAonBto contain a low-5 degree without containing0.

**Local computability and uncountable structures,**
book chapter,
in the ASL *Lecture Notes in Logic* volume 41,
*Effective Mathematics of the Uncountable*,
eds. N. Greenberg, J.D. Hamkins, D.R. Hirschfeldt, & R.G. Miller
(Cambridge University Press, 2013), 81-123.
pdf download

Abstract:This is a chapter-length introduction to local computability, a method of using Turing computation to consider uncountable structures by looking at their finitely generated substructures.

**The cardinality of an oracle in Blum-Shub-Smale computation**
(with W. Calvert and K. Kramer), *Proceedings:
Seventh International Conference on
Computability and Complexity in Analysis*,
eds. X. Zheng & N. Zhong,
*Electronic Proceedings in Theoretical Computer Science*
**24**, 56-66.
See also the full version of this article immediately below.
pdf download

**Noncomputable functions in the Blum-Shub-Smale model**
(with W. Calvert and K. Kramer),
full version in *Logical Methods in Computer Science*
**2** (2011) 15, 1-20
pdf download
(extension of the research abstract above); and
version for the abstract booklet for the conference *Logical
Approaches to Barriers in Computing and Complexity*
(17-20 February 2010, Greifswald, Germany)
pdf download.

Abstract:We examine the relation of BSS-reducibility on subsets of the real numbers. The question was asked recently (and anonymously) whether it is possible for the halting problemHin BSS-computation to be BSS-reducible to a countable set. Intuitively, it seems that a countable set ought not to contain enough information to decide membership in a reasonably complex (uncountable) set such asH. We confirm this intuition, and prove a more general theorem linking the cardinality of the oracle set to the cardinality, in a local sense, of the set which it computes. We also mention other recent results on BSS-computation and algebraic real numbers: notably, that the setA_dof algebraic numbers of degree at mostdis not decidable inA_(d-1). This answers a question of Meer and Ziegler.

**Computably categorical fields via Fermat's Last Theorem,**
(with H. Schoutens),
*Computability*
**2** (2013) 1, 51-65.
pdf download

Abstract:We construct a computable, computably categorical field of infinite transcendence degree over the rationals, using the Fermat polynomials and assorted results from algebraic geometry. We also show that this field has an intrinsically computable (infinite) transcendence basis.

**Adapting Rabin's Theorem for differential fields**
(with A. Ovchinnikov), in
*Models of Computation in Context -- CiE 2011*,
eds. B. Loewe, D. Normann, I. Soskov, & A. Soskova,
*Lecture Notes in Computer Science* **6735**
(Berlin: Springer-Verlag, 2011), 211-220.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Harrington extended the first half of Rabin's Theorem to differential fields, proving that every computable differential field can be viewed as a computably enumerable subfield of a computable presentation of its differential closure. For fieldsF, the second half of Rabin's Theorem says that this subfield is Turing-equivalent to the set of irreducible polynomials inF[X]. We investigate possible extensions of this second half, asking both about the degree of the differential fieldKwithin its differential closure and about the degree of the set of constraints forK, which forms the closest analogue to the set of irreducible polynomials.

**Computing constraint sets for differential fields**
(with A. Ovchinnikov and D. Trushin),
*Journal of Algebra*.
(2014) 407, 316-357.
This article is an extension of the one immediately above.
pdf download

Abstract:Kronecker's Theorem and Rabin's Theorem are fundamental results about computable fieldsFand the decidability of the set of irreducible polynomials overF. We adapt these theorems to the setting of differential fieldsK, with constrained pairs of differential polynomials overKassuming the role of the irreducible polynomials. We prove that two of the three basic aspects of Kronecker's Theorem remain true here, and that the reducibility in one direction (but not the other) from Rabin's Theorem also continues to hold.

**Computable differential fields,**
report written for the week in Computability Theory
at the Mathematisches Forschungsinstitut Oberwolfach,
Feb. 5-11, 2012.
This is a summary of results from the article immediately above.
pdf download

Abstract:We state and describe recent results on computable differential fields, focusing on our attempts to formulate and prove analogues of Kronecker's Theorem and Rabin's Theorem for this class of structures. Proofs are omitted in this short report, but a substantial introduction to differential fields is included. This is joint work with Alexey Ovchinnikov and Dmitry Trushin.

**The hierarchy of equivalence relations on the
natural numbers under computable reducibility,**
(with S. Coskey and J. Hamkins),
*Computability*
**1** (2012) 1, 15-38.
pdf download

Abstract:We define and elaborate upon the notion of computable reducibility between equivalence relations on the natural numbers, providing a natural computable analogue of Borel reducibility, and investigate the hierarchy to which it gives rise. 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.

**Approximating functions and measuring distance on a graph**
(with W. Calvert and J. Chubb Reimann),
in the *Proceedings of the 12th Asian Logic Conference, 2011*
(Singapore: World Scientific Publishing Company, 2013), 24-52.
pdf download

Abstract:We apply the techniques of computable model theory to the distance function of a graph. This task leads us to adapt the definitions of several truth-table reducibilities so that they apply to functions as well as to sets, and we prove assorted theorems about the new reducibilities and about functions which have nonincreasing computable approximations. Finally, we show that the spectrum of the distance function can consist of an arbitrary single 1-btt degree which is approximable from above, or of all such 1-btt degrees at once, or of the 1-btt degrees of exactly those functions approximable from above in at mostnsteps.

**Computable categoricity for algebraic fields with
splitting algorithms,**
(with A. Shlapentokh),
*Transactions of the American Mathematical Society*
**367** (2015) 6, 3981--4017.
pdf download

Abstract:A computably presented algebraic fieldFhas asplitting algorithmif it is decidable which polynomials inF[X]are irreducible there. We prove that such a field is computably categorical iff it is decidable which pairs of elements ofFbelong to the same orbit under automorphisms. We also show that this criterion is equivalent to the relative computable categoricity ofF.

**Categoricity properties for computable algebraic fields**
(with D. Hirschfeldt, K. Kramer, and A. Shlapentokh),
*Transactions of the American Mathematical Society*
**367** (2015) 6, 3955--3980.
pdf download

Abstract:We examine categoricity issues for computable algebraic fields. Such fields behave nicely with regard to relative computable categoricity, as we find a fairly natural structural criterion for them to be relatively computably categorical. However, their behavior with regard to computable categoricity is less nice: we use our criterion to construct a field that is computably categorical, but not relatively computably categorical. Finally, we show that computable categoricity for this class of fields isΠ-complete.^{0}_{4}

**Complexity of equivalence relations and preorders from computability theory**
(with G. Ianovski, K.M. Ng, and A. Nies),
*Journal of Symbolic Logic* **79** (2014) 3, 859--881.
(Copyright held by the Association for Symbolic Logic.)
pdf download

Abstract:We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsRandS, a componentwise reducibility is defined byR≤S↔∃ f ∀x, y [xRy ↔ f(x) Sf(y)].Herefis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is aΠ-complete equivalence relation, but no_{1}Π-complete for_{k}k≥2. We show that theΣpreorders arising naturally in the above-mentioned areas are_{k}Σ-complete. This includes polynomial time_{k}m-reducibility on exponential time sets, which isΣ, almost inclusion on r.e. sets, which is_{2}Σ, and Turing reducibility on r.e. sets, which is_{3}Σ._{4}

**Finitary reducibility on equivalence relations**
(with K.M. Ng), to appear in the *Journal of Symbolic Logic*.
pdf download

Abstract:We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be Π-complete under computable reducibility, we show that, for every_{n+2}n, there does exist a natural equivalence relation which is Π-complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy. We also refute a possible generalization of Myhill's Theorem._{n+2}

**Local computability for ordinals**
(with J. Franklin, A. Kach and R. Solomon), in
*The Nature of Computation: 9th Conference on Computability in Europe, CiE 2013*,
eds. P. Bonizzoni, V. Brattka, and B. Löwe,
*Lecture Notes in Computer Science* **7921**
(Berlin: Springer-Verlag, 2013), 161-170.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:We examine the extent to which well orders satisfy the properties of local computability, which measure how effectively the finite suborders of the ordinal can be presented. Known results prove that all computable ordinals are perfectly locally computable, whereasωand larger countable ordinals are not. We show that perfect local computability also fails for uncountable ordinals, and that ordinals_{1}^{CK}α≥ωare_{1}^{CK}θ-extensionally locally computable for allθ<ω, but not when_{1}^{CK}θ>ω, nor when_{1}^{CK}θ=ω._{1}^{CK}≤α<ω_{1}^{CK}_{˙ }ω

**Classes of structures with universe a subset of ω_{1}**
(with E. Fokina, S.-D. Friedman, and J.F. Knight),

Abstract:We continue recent work on computable structure theory in the setting ofω. We prove the analogue of an earlier result saying that isomorphism of computable structures lies "on top" among_{1}Σequivalence relations on^{}_{1}ω. Our equivalence relations are onω. In the standard setting,_{1}Σsets are characterized in terms of paths through trees. In the setting of^{}_{1}ω, we use a new characterization of_{1}Σsets that involves clubs in^{}_{1}ω. Finally, we present some new results about_{1}ω-computable categoricity for fields._{1}

**Isomorphisms of non-standard fields
and Ash's Conjecture**
(with R. Dimitrov, V. Harizanov, and K.J. Mourad), in
*Language, Life, Limits: 10th Conference on Computability
in Europe, CiE 2014*,
eds. A. Beckmann, E. Csuhaj-Varju, and K. Meer,
*Lecture Notes in Computer Science* **8493**
(Berlin: Springer-Verlag, 2014), 143-152.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Cohesive sets play an important role in computability theory. Here we use cohesive sets to build nonstandard versions of the rationals. We use Koenigsmann's work on Hilbert's Tenth Problem to establish that these nonstandard fields are rigid. As a consequence we obtain results about automorphisms of the lattices of computably enumerable vector spaces arising in the context of Ash's conjecture.

**Effective symmetry breaking**
(with R. Solomon and R.M. Steiner), in
*Language, Life, Limits: 10th Conference on Computability
in Europe, CiE 2014*,
eds. A. Beckmann, E. Csuhaj-Varju, and K. Meer,
*Lecture Notes in Computer Science* **8493**
(Berlin: Springer-Verlag, 2014), 314-323.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:Symmetry breaking involves coloring the elements of a structure so that the only automorphism which respects the coloring is the identity. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize ton-colorings for fixednand for variablen.

**Turing degree spectra of differentially closed fields**
(with D. Marker), to appear in the *Journal of Symbolic Logic*.
pdf download

Abstract:The degree spectrum of a countable structure is the set of all Turing degrees of presentations of that structure. We show that every nonlow Turing degree lies in the spectrum of some differentially closed field (of characteristic 0, with a single derivation) whose spectrum does not contain the computable degree. Indeed, this is an equivalence, for we also show that every such field of low degree is isomorphic to a computable differential field. Relativizing the latter result and applying a theorem of Montalbán, Soskova, and Soskov, we conclude that the spectra of countable differentially closed fields of characteristic 0 are exactly the jump-preimages of spectra of automorphically nontrivial countable graphs.0

**Effective classification of computable structures**
(with K. Lange and R. Steiner), to appear in the *Notre Dame Journal of Formal Logic*.
pdf download

Abstract:Letbe a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures fromKsuch that every structure inKis isomorphic to exactly one structure on the list. Such a list is called aKcomputable classificationof, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields, and that with aK-oracle, we can obtain similar classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields.0'

**A computable functor from graphs to fields**
(with B. Poonen, H. Schoutens, and A. Shlapentokh),
submitted for publication.
pdf download

Abstract:We construct a fully faithful functor from the category of graphs to the category of fields. Using this functor, we resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structureS, there exists a countable fieldFwith the same essential computable-model-theoretic properties asS. Along the way, we develop a new notion of "computable category theory," and prove that our functor and its partially-defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.

**Computable functors and effective interpretability**
(with M. Harrison-Trainor, A. Melnikov, and A. Montalbán),
to appear in the *Journal of Symbolic Logic*.
pdf download

Abstract:Our main result is the equivalence of two notions of reducibility between structures. One is a syntactical notion which is an effective version of interpretability as in model theory, and the other one is a computational notion which is a strengthening of the well-known Medvedev reducibility. We extend our result to effective bi-interpretability and also to effective reductions between classes of structures.

**On computable field embeddings and difference closed fields**
(with M. Harrison-Trainor and A. Melnikov), to appear in the
*Canadian Journal of Mathematics*.
pdf download

Abstract:We investigate when a computable automorphism of a computable field can be effectively extended to a computable automorphism of its (computable) algebraic closure. We then apply our results and techniques to study effective embeddings of computable difference fields into computable difference closed fields.

**As easy as Q: Hilbert's Tenth Problem for subrings of the rationals and number fields**
(with K. Eisenträger, J. Park, and A. Shlapentokh),
to appear in the *Transactions of the American Mathematical Society*.
pdf download

Abstract:Hilbert's Tenth Problem over the rationals is one of the biggest open problems in the area of undecidability in number theory. In this paper we construct new, computably presentable subringsR ⊂having the property that Hilbert's Tenth Problem forQR, denotedHTP(R), is Turing equivalent toHTP(. We are able to put several additional constraints on the ringsQ)Rthat we construct. Given any computable nonnegative real numberr ≤ 1we construct such ringsR=withZ[S^{-1}]Sa set of primes of lower densityr. We also construct examples of ringsRfor which deciding membership inRis Turing equivalent to decidingHTP(R)and also equivalent to decidingHTP(. Alternatively, we can makeQ)HTP(R)have arbitrary computably enumerable degree aboveHTP(. Finally, we show that the same can be done for subrings of number fields and their prime ideals.Q)

**Baire category theory for Hilbert's Tenth Problem inside Q**,
in *Pursuit of the Universal: 12th Conference on Computability
in Europe, CiE 2016*,
eds. A. Beckmann, L. Bienvenu, and N. Jonoska,
*Lecture Notes in Computer Science* **9709**
(Berlin: Springer-Verlag, 2016), 343-352.
(Copyright held by Springer-Verlag.)
pdf download

Abstract:For a ringR, Hilbert's Tenth ProblemHTP(R)is the set of polynomial equations overR, in several variables, with solutions inR. We consider computability of this set for subringsRof the rationals. Applying Baire category theory to these subrings, which naturally form a topological space, relates their setsHTP(R)to the setHTP(, whose decidability remains an open question. The main result is that, for an arbitrary setQ)C,HTP(computesQ)Cif and only if the subringsRfor whichHTP(R)computesCform a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model of, and for existential definability ofZ.Z

**Measure theory and Hilbert's Tenth Problem inside Q**,
in *Sets and Computations*,
eds. S.D. Friedman, D. Raghavan, & Y. Yang,
vol. 33 of the Lecture Note Series of the Institute for Mathematical Sciences,
National University of Singapore
(Singapore: World Scientific, 2017), 253-269.
(Copyright held by the National University of Singapore.)
pdf download

Abstract:For a ringR, Hilbert's Tenth ProblemHTP(R)is the set of polynomial equations overR, in several variables, with solutions inR. WhenR=, it is known that the jumpZZ′is Turing-reducible toHTP(. We consider computability ofZ)HTP(R)for subringsRof the rationals. Applying measure theory to these subrings, which naturally form a measure space, relates their setsHTP(R)to the setHTP(, whose decidability remains an open question. We raise the question of the measure of the topological boundary of the solution set of a polynomial within this space, and show that if these boundaries all have measure 0, then for each individual oracle Turing machine Φ, the reductionQ)R′=Φfails on a set of subrings of positive measure. That is, no Turing reduction of the jump^{HTP(R)}R′of a subringRtoHTP(R)holds uniformly on a set of measure 1.

**Revisiting uniform computable categoricity:
for the sixtieth birthday of Prof. Rod Downey**,
in *Computability and Complexity: Essays Dedicated to Rodney G. Downey
on the Occasion of His Sixtieth Birthday*,
eds. A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, & F. Rosamond,
*Lecture Notes in Computer Science* **10010** (Berlin: Springer-Verlag, 2017), 254--270.
pdf download

Abstract:Inspired by recent work of Csima and Harrison-Trainor and of Montalbán in relativizing the notion of degrees of categoricity, we return to uniform computable categoricity, as described in work of Downey, Hirschfeldt and Khoussainov. Our attempt to integrate these notions together leads to certain new questions about relativizing the concept of the jump of a structure, as well as to an idea of the structural information content of a countable structure, i.e., that information which can be recovered uniformly from copies of the structure.

**Computable transformations of structures**,
in *Unveiling Dynamics and Complexity: 13th Conference on Computability in Europe, CiE 2017*, eds. J. Kari, F. Manea, & I. Petre,
*Lecture Notes in Computer Science* **10307**
(Berlin: Springer-Verlag, 2017), 88--97.
pdf download

Abstract:The isomorphism problem, for a class of structures, is the set of pairs of structures within that class which are isomorphic to each other. Isomorphism problems have been well studied for many classes of computable structures. Here we consider isomorphism problems for broader classes of countable structures, using Turing functionals and applying the notions of finitary and countable computable reductions which have been developed for equivalence relations more generally.

**Turing degree spectra of real closed fields**
(with V. Ocasio González),
submitted for publication.
pdf download

Abstract:Several researchers have recently established that for every Turing degreec, the real closed field of allc-computable real numbers has spectrum {d:d′≥c″}. We investigate the spectra of real closed fields further, focusing first on subfields of the fieldRof computable real numbers, then on archimedean real closed fields more generally, and finally on non-archimedean real closed fields. For each noncomputable, computably enumerable set_{0}C, we produce a real closedC-computable subfield ofRwith no computable copy. Then we build an archimedean real closed field with no computable copy but with a computable enumeration of the Dedekind cuts it realizes, and a computably presentable nonarchimedean real closed field whose residue field has no computable presentation._{0}

**Computable reducibility for Cantor space**,
submitted for publication.
pdf download

Abstract:We examine various versions of Borel reducibility on equivalence relations on the Cantor space2, using reductions given by Turing functionals on the inputs^{ω}A ∈ 2. In some versions, we vary the number of jumps of^{ω}Awhich the functional is allowed to use. In others, we do not require the reduction to succeed for all elements of the Cantor space at once, but only when applied to arbitrary finite or countable subsets of2. In others we allow an arbitrary oracle set in addition to the inputs. All of these versions, inspired largely by work on computable reducibility on equivalence relations on^{ω}ω, combine to yield a rich set of options for evaluating the precise level of difficulty of a Borel reduction, or the reasons why a Borel reduction may fail to exist.

**Borel functors and infinitary interpretations**
(with M. Harrison-Trainor and A. Montalbán),
submitted for publication.
pdf download

Abstract:We introduce the notion of infinitary interpretation of structures. In general, an interpretation between structures induces a continuous homomorphism between their automorphism groups, and furthermore, it induces a functor between the categories of copies of each structure. We show that for the case of infinitary interpretation the reversals are also true: every Baire-measurable homomorphism between the automorphism groups of two countable structures is induced by an infinitary interpretation, and every Baire-measurable functor between the set of copies of two countable structures is induced by an infinitary interpretation. Furthermore, we show the complexities are maintained in the sense that if the functor isΔ, then the interpretation that induces it is_{α}Δ^{in}up to_{α}equivalence.Δ_{α}

**Isomorphism and classification for countable structures**,
submitted for publication.
pdf download

Abstract:We introduce a topology on the space of all isomorphism types represented in a given class of countable models, and use this topology as an aid in classifying the isomorphism types. This mixes ideas from effective descriptive set theory and computable structure theory, extending concepts from the latter beyond computable structures to examine the isomorphism problem on arbitrary countable structures. We give examples using specific classes of fields and of trees, illustrating how the new concepts can yield classifications that reveal differences between seemingly similar classes. Finally, we use a computable homeomorphism to define a measure on the space of isomorphism types of algebraic fields, and examine the prevalence of relative computable categoricity under this measure.

**On existential definitions of c.e. subsets of rings of functions
of characteristic 0,**
(with A. Shlapentokh),
submitted for publication.
pdf download

Abstract:We extend results of Denef, Zahidi, Demeyer and the second author to show the following.

(1) Rational integers have a single-fold Diophantine definition over the ring of integral functions of any function field of characteristic 0.

(2) Every c.e. set of integers has a finite-fold Diophantine definition over the ring of integral functions of any function field of characteristic 0.

(3) All c.e. subsets of polynomial rings over totally real number fields have finite-fold Diophantine definitions. (These are the first examples of infinite rings with this property.)

(4) LetKbe a one-variable function field over a number field and letpbe any prime ofK. Then the valuation ring ofphas a Diophantine definition.

(5) LetKbe a one-variable function field over a number field and letSbe a finite set of its primes. Then all c.e. subsets ofO(K;S)are existentially definable. (HereO(K;S)is the ring ofS-integers or a ring of integral functions.)

**Computable fields and Galois theory**, in the
*Notices of the American Mathematical Society*
**55** (August 2008) 7, 798-807;
Chinese translation in *Mathematical Advances in Translation*
(2010) 4, 319-330.
(Copyright held by the American Mathematical Society.)
pdf download

Abstract:This expository article introduces the notion of a computable field and shows how computability theory may be used to prove that for certain processes, related to Galois theory and finding roots of polynomials, we can build computable fields in which there is no algorithm which accomplishes these processes.

**Computability and differential fields: a tutorial**,
to appear in
*Differential Algebra and Related Topics:
Proceedings of the Second International Workshop*,
eds. L. Guo and W. Sit.
pdf download

Abstract:This article complements the articleComputable Fields and Galois Theoryabove, offering further results on computable fields and processes which cannot be performed by any algorithm. The notation and definitions used in the two articles are identical, and both are intended to introduce computable model theory to mathematicians outside of mathematical logic. This article evolved from a tutorial presentation at the DART II workshop (Differential Algebra and Related Topics) in April 2007, and considers a few questions related to differential fields, in addition to traditional fields.

PhD. Dissertation: **Computability, Definability, Categoricity, and
Automorphisms** (supervised by R. Soare).

pdf download

Degrees of maximal independent subsets of free groups, with C. McCoy.

Measure theory and Hilbert's Tenth Problem for subrings of the rationals, with A. Shlapentokh.

Decidability of the constraint set for a constant differential field, with A. Ovchinnikov.

Blum-Shub-Smale computation and generalizations to algebraic structures, assorted projects with W. Calvert, C. Gassner, K. Kramer, A. Pauly, M. Ziegler, and others.

The papers above are copyrighted and may be downloaded and/or printed only for personal or non-profit educational use.

Most of the more recent papers are also available from the arXiv.