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.
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.
(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.
(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.
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),
to appear in the
Archive for Mathematical Logic.
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.
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.
Is it harder to factor a polynomial
or to find a root?
to appear in the
Transactions of the American Mathematical Society.
(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),
to appear in the
Archive for Mathematical Logic.
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),
to appear in Algebra and Logic.
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.
Computing the fundamental group of an R-computable manifold
(with W. Calvert),
submitted for publication.
pdf download
Abstract: Using the model of computability developed by Blum, Cucker, Shub, and Smale for the real numbers R, we investigate the difficulty of determining the answers to several basic topological questions about manifolds. Under natural definitions of R-computable manifold and R-computable path, we show that, while BSS machines cannot in general decide such questions as nullhomotopy and simple connectedness for such structures, there are nevertheless R-computable presentations of paths and homotopy equivalence classes under which such computations are possible. Indeed, we argue that the appropriate model of computation for homotopy questions is the Turing model, not the BSS model for R.
Computability of Fraisse limits
(with B. Csima, V. Harizanov, and A. Montalban),
submitted for publication.
pdf download
Abstract: Fraisse 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 Fraisse limit. We also show that degree spectra of relations on a sufficiently nice Fraisse limit are always upward closed unless the relation is definable by a quantifier-free formula. We give some sufficient or necessary conditions for a Fraisse limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal.
Computably categorical fields via Fermat's Last Theorem,
(with H. Schoutens),
submitted for publication.
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.
Degree spectra of high-n and nonlow-n degrees
(with A. Frolov, V. Harizanov, I. Kalimullin, and O. Kudinov),
submitted for publication.
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.
Local computability and uncountable structures,
book chapter,
submitted for publication.
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.
Computable fields and Galois theory, in the
Notices of the American Mathematical Society
55 (August 2008) 7, 798-807.
(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
Computable categoricity for algebraic fields, with A. Shlapentokh.
Relative BSS-computability of sets of algebraic real numbers, with W. Calvert.
Group theory and computable algebra, with D. Kahrobaei.