Russell Miller: Research and Publications

Research and Publications

Prof. Russell Miller


Research Interests

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.


Publications


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 degree 0 from 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 not 0. 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 be spectrally 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 degrees c such that c' computes 0''.

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 a locally 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 to 0. 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 of ITRM-clockable ordinals corresponding 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 real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not n lies in r with 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, the splitting set S is the set of polynomials p(X) in F[X] which factor over F, and the root set R 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 are d-computably categorical for a particular Turing degree d with d'=0'', but that not all such fields are 0'-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 extension F of Q or Z/(p) may be regarded either as a structure in its own right, or as a subfield of its algebraic closure E. We consider the Turing degree spectrum of F in both cases, as a structure and as a relation on E, and characterize the sets of Turing degrees that are realized as such spectra. The results show a connection between enumerability in the structure F and computability when F is seen as a subfield of E.

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 structure M to be the least degree d for which M is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0^(n) can be so realized, as can the degree 0^(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 the automorphism spectrum of a computable structure M, a measurement of the complexity of the symmetries of M, 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-n degrees can be such a spectrum, and likewise for the set of nonlow-n degrees. We then repeat these questions specifically for linear orders and for relations on the computable dense linear order Q. New results include realizations of the set of nonlow-n Turing degrees as the spectrum of a relation on Q for all n > 0, and a realization of the set of nonlow-n Turing degrees as the spectrum of a linear order whenever n > 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 the age of 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 the Fraï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 degree 0; 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 algebra B. For such subalgebras A, we show that it is possible for the spectrum of the unary relation A on B to contain a low-5 degree without containing 0.

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 problem H in 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 as H. 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 set A_d of algebraic numbers of degree at most d is not decidable in A_(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 fields F, the second half of Rabin's Theorem says that this subfield is Turing-equivalent to the set of irreducible polynomials in F[X]. We investigate possible extensions of this second half, asking both about the degree of the differential field K within its differential closure and about the degree of the set of constraints for K, 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 fields F and the decidability of the set of irreducible polynomials over F. We adapt these theorems to the setting of differential fields K, with constrained pairs of differential polynomials over K assuming 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 most n steps.

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 field F has a splitting algorithm if it is decidable which polynomials in F[X] are irreducible there. We prove that such a field is computably categorical iff it is decidable which pairs of elements of F belong to the same orbit under automorphisms. We also show that this criterion is equivalent to the relative computable categoricity of F.

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 Π04-complete.

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 relations R and S, a componentwise reducibility is defined by R≤S↔∃ f ∀x, y [xRy ↔ f(x) Sf(y)]. Here f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a Π1-complete equivalence relation, but no Πk-complete for k≥2. We show that the Σk preorders arising naturally in the above-mentioned areas are Σk-complete. This includes polynomial time m-reducibility on exponential time sets, which is Σ2, almost inclusion on r.e. sets, which is Σ3, and Turing reducibility on r.e. sets, which is Σ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 Πn+2-complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is Πn+2-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.

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 ω1CK and larger countable ordinals are not. We show that perfect local computability also fails for uncountable ordinals, and that ordinals α≥ω1CK are θ-extensionally locally computable for all θ<ω1CK, but not when θ>ω1CK, nor when θ=ω1CK≤α<ω1CK˙ ω.

Classes of structures with universe a subset of ω1 (with E. Fokina, S.-D. Friedman, and J.F. Knight), Journal of Logic and Computation 23 (2013) 6, 1249-1265. pdf download; and the earlier Classes of structures with universe a subset of ω1 (with E. Fokina, S.-D. Friedman, J.F. Knight, and A. Montalbán), in The Infinity Project: A 2009-2011 Research Programme, eds. S.-D. Friedman, M. Koerwien, & M. Müller, CRM Documents 11 (Bellaterra, Barcelona: Centre de Recerca Matemática, 2012), 39-50. pdf download.

Abstract: We continue recent work on computable structure theory in the setting of ω1. We prove the analogue of an earlier result saying that isomorphism of computable structures lies "on top" among Σ1 equivalence relations on ω. Our equivalence relations are on ω1. 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.

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 to n-colorings for fixed n and for variable n.

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

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

Abstract: Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, 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 a 0'-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.

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 structure S, there exists a countable field F with the same essential computable-model-theoretic properties as S. 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 subrings R ⊂ Q having the property that Hilbert's Tenth Problem for R, denoted HTP(R), is Turing equivalent to HTP(Q). We are able to put several additional constraints on the rings R that we construct. Given any computable nonnegative real number r ≤ 1 we construct such rings R=Z[S-1] with S a set of primes of lower density r. We also construct examples of rings R for which deciding membership in R is Turing equivalent to deciding HTP(R) and also equivalent to deciding HTP(Q). Alternatively, we can make HTP(R) have arbitrary computably enumerable degree above HTP(Q). Finally, we show that the same can be done for subrings of number fields and their prime ideals.

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 ring R, Hilbert's Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. We consider computability of this set for subrings R of the rationals. Applying Baire category theory to these subrings, which naturally form a topological space, relates their sets HTP(R) to the set HTP(Q), whose decidability remains an open question. The main result is that, for an arbitrary set C, HTP(Q) computes C if and only if the subrings R for which HTP(R) computes C form a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model of Z, and for existential definability of 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 ring R, Hilbert's Tenth Problem HTP(R) is the set of polynomial equations over R, in several variables, with solutions in R. When R=Z, it is known that the jump Z′ is Turing-reducible to HTP(Z). We consider computability of HTP(R) for subrings R of the rationals. Applying measure theory to these subrings, which naturally form a measure space, relates their sets HTP(R) to the set HTP(Q), 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 reduction R′=ΦHTP(R) fails on a set of subrings of positive measure. That is, no Turing reduction of the jump R′ of a subring R to HTP(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 degree c, the real closed field of all c-computable real numbers has spectrum {d : d′c″}. We investigate the spectra of real closed fields further, focusing first on subfields of the field R0 of 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 C, we produce a real closed C-computable subfield of R0 with 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.

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

Abstract: We examine various versions of Borel reducibility on equivalence relations on the Cantor space 2ω, using reductions given by Turing functionals on the inputs A ∈ 2ω. In some versions, we vary the number of jumps of A which 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 of 2ω. 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) Let K be a one-variable function field over a number field and let p be any prime of K. Then the valuation ring of p has a Diophantine definition.
(5) Let K be a one-variable function field over a number field and let S be a finite set of its primes. Then all c.e. subsets of O(K;S) are existentially definable. (Here O(K;S) is the ring of S-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 article Computable Fields and Galois Theory above, 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

Current Projects

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.