The complexity of computable categoricity for algebraic fields,
contributed talk at the Logic Colloquium
(July 11, 2011; University of Barcelona, Catalunya, Spain.)
pdf download
Abstract: A computable structure A is computably categorical if every computable structure B classically isomorphic to A is in fact computably isomorphic to A. We present recent results on this topic, focusing on our proof that the property of computable categoricity for computable algebraic fields is Pi^0_4-complete. (A field is algebraic if it is an algebraic extension of its prime subfield.) It follows that there exists a computably categorical algebraic field F for which the more general property of relative computable categoricity fails. This F is in some sense pathological. We describe a structural Sigma^0_3 condition which is equivalent to relative computable categoricity. On the other hand, we will also explain why the separate pathological situation of finite computable dimension greater than 1 is impossible for these fields: every computable algebraic field either is computably categorical or else has infinitely many computable isomorphism classes. This is joint work with Denis Hirschfeldt, Ken Kramer, and Alexandra Shlapentokh.
Adapting Rabin's Theorem for differential fields,
invited talk in the Special Session on Computability
in Algebra, Analysis, and Geometry,
at the meeting Computability in Europe
(June 28, 2011; Sofia University, Bulgaria.)
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. This is joint work with Alexey Ovchinnikov.
Boolean Subalgebras and Computable Copies,
contributed talk at the ASL Annual Meeting
(March 25, 2011; University of California Berkeley.)
pdf download
Abstract: It is known from the work referenced below 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. That is, A is a low-5 Boolean subalgebra of B, but B has no computable Boolean subalgebra C with (B, C) isomorphic to (B, A).
[1] R.G. Downey & C.G. Jockusch, Jr., Every low Boolean algebra is isomorphic to a recursive one, Proceedings of the American Mathematical Society, vol. 122 (1994), pp. 871--880.
[2] J.F. Knight & M. Stob, Computable Boolean algebras, Journal of Symbolic Logic, vol. 65 (2000), pp. 1605-1623.
[3] J.J. Thurber, Every low-2 Boolean algebra has a recursive copy, Proceedings of the American Mathematical Society, vol. 123 (1995), pp. 3859--3866.
Computation on the Real Numbers
and Other Uncountable Domains,
from the University of Connecticut Logic Group seminar,
25 February 2011.
pdf download
Abstract: We introduce three different models for computation in the uncountable setting: ordinal-time computation, computable analysis, and Blum-Shub-Smale computation. We then compare and contrast these models, discussing the benefits, drawbacks, and motivations of each along the way.
Boolean Subalgebras of the Computable Atomless Boolean Algebra,
from the University of Chicago Logic Seminar,
12 January 2011.
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.
The proof uses techniques similar to those from recent joint work on linear orders in [1]. We will introduce the Boolean-algebra result by describing that work, which shows that there exists a unary relation on the computable dense linear order whose spectrum (as a relation) contains precisely the non-low Turing degrees.
[1] A. Frolov, V. Harizanov, I. Kalimullin, O. Kudinov, & R. Miller; Degree Spectra of High-n and Non-low-n Degrees, Journal of Logic and Computation. Advance Access published November 29, 2010, doi: 10.1093/logcom/exq041.
Algebraic Fields and Computable Categoricity,
from George Washington University Logic Seminar,
19 November 2010.
pdf download
Abstract: A computable structure A is computably categorical if for every computable B classically isomorphic to A, there exists a computable isomorphism from A onto B. For many classes of computable structures, structural characterizations of this property have been established. We start to do the same for fields, by considering the case of an algebraic field F with a splitting algorithm, i.e. such that the set of irreducible polynomials in F[X] is computable. We prove that such a field is computably categorical if and only if its orbit relation G = {(a,b) : there exists h in Aut(F) with h(a)=b} is computable. With F algebraic, the orbit relation G can also be defined by an AE-formula in the language of fields. Ostensibly, the condition given above is therefore Sigma-4, but since F is assumed to have a splitting algorithm, computability of G is in fact Sigma-3. This is joint work with Denis Hirschfeldt, Ken Kramer, and Alexandra Shlapentokh.
Computable Fields and their Algebraic Closures,
from WCT, the Workshop on Computability Theory
(July 6, 2010; Universidade dos Acores,
Ponta Delgada, Portugal.)
pdf download
Abstract: We present recent results about computable fields F and embeddings of F into its algebraic closure. We focus on fields which are algebraic over their prime subfields. The discussion begins with a review of Rabin's Theorem, and continues with more exact computability-theoretic comparisons of the set of irreducible polynomials in F[X], the set of polynomials there with roots in F, and the different ways F can sit within computable presentations of its algebraic closure. We also examine this issue for noncomputable fields, considering the spectrum of the field F and its spectrum as a relation on the algebraic closure. The recent results presented are the work of Frolov, Kalimullin, Steiner, and the speaker, in various combinations.
The Cardinality of an Oracle in Blum-Shub-Smale Computation,
from CCA, the Seventh International Conference on Computability
and Complexity in Analysis
(June 23, 2010; Jiangsu University,
Zhenjiang, China.)
pdf download
Abstract: This is joint work with Wesley Calvert and Ken Kramer. 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.
Noncomputable Functions in the Blum-Shub-Smale Model,
from the conference Logical Approaches to Computational Barriers
(February 18, 2010; Alfried Krupp Wissenschaftskolleg,
Greifswald, Germany.)
pdf download
Abstract: This is joint work with Wesley Calvert and Ken Kramer. We answer several questions of Meer and Ziegler about the Blum-Shub-Smale model of computation on the real numbers: the set A(d) of algebraic numbers of degree at most d is not decidable in A(d-1), and the BSS halting problem is not decidable in any countable oracle.
Real Computable Manifolds and Homotopy Groups,
from the Eighth Conference on Unconventional Computation
(September 10, 2009; Universidade dos Acores,
Ponta Delgada, Portugal.)
pdf download
Abstract: This is joint work with Wesley Calvert. 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. Indeed, the appropriate setting for investigation of the fundamental group turns out to be Turing computability, rather than real computability.
BSS machines: computability without search procedures,
from the Second CUNY Workshop on
Effective Mathematics of the Uncountable
(August 19, 2009; CUNY Graduate Center, New York, NY.)
pdf download
Abstract: Blum-Shub-Smale machines act on tuples of real numbers, treating each x in R as an atomic object, rather than as a Dedekind cut, a Cauchy sequence, or a subset of the natural numbers. Such machines run according to finite programs, using finitely many real parameters; they can perform comparisons (< and =) and compute any standard binary operation in a single step. Since their computations are required to halt within finitely many steps, they cannot search through the entire domain R^n, unlike standard Turing machines, which can search through omega^n. We exploit this difference to show that for polynomials in R[X], although factorizability is (easily) BSS-decidable, there are no BSS algorithms for finding the factors, nor for determining roots in R or C. We also give a (significantly more involved) proof that the set of algebraic real numbers of degree d+1 over the rationals is not BSS-decidable from an oracle for the set of algebraic reals of degree less than or equal to d. This answers a question of Meer and Ziegler.Some of this work is joint with Wesley Calvert.
Survey of degree spectra of high-n
and non-low-n degrees,
contributed talk at the ASL European Summer Meeting
(July 31, 2009; Sofia University, Bulgaria.)
pdf download
Abstract: For every n, both the class of high-n Turing degrees and the class of non-low-n Turing degrees are upwards-closed under Turing reducibility, so it is natural to search for structures with spectra equal to various of these classes. We give a survey of recent results on this topic, by the speaker and many other authors, and also consider the same question for spectra of relations on computable structures. Linear orders turn out to be of particular interest.
Spectra of algebraic fields and subfields,
invited talk in the Special Session on Computational Model Theory
at the meeting Computability in Europe
(July 20, 2009; Ruprecht-Karls-Universitat Heidelberg, Germany.)
pdf download
Abstract: An algebraic field extension F of a prime field may be regarded either as a structure in its own right, or as a subfield of its algebraic closure. We consider the Turing degree spectrum of F in both cases, as a structure and as a relation on its (computable) algebraic closure, 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 the algebraic closure. This is joint work with Andrey Frolov and Iskander Kalimullin.
Computably categorical fields via Fermat's Last Theorem,
invited talk in the Special Session on Computability Theory,
at the ASL North American Annual Meeting
(May 22, 2009; Notre Dame University, South Bend, IN.)
pdf download
Abstract: This is joint work with Hans Schoutens. We construct a computable field F which has infinite transcendence degree over the rationals Q, yet is computably categorical. The key is to be able to enumerate an image of the original transcendence basis in every computable copy F' of the field, and we adjoin solutions of the Fermat polynomials to enable this enumeration. Fermat's theorem shows that no nontrivial solution of these polynomials will lie in Q, and results from algebraic geometry further restrict the possible solutions, to the point that the solutions we do find in F' must yield the desired basis.
Real computability and manifolds,
invited talk in the Special Session on Orderings in Logic and Topology,
at the AMS National Meeting
(January 8, 2009; Washington, DC.)
pdf download
Abstract: We use the Blum-Shub-Smale notion of computability on real numbers to produce a reasonable definition of real-computable manifolds. We then consider questions about the decidability of simple connectedness of the manifold itself, and of nullhomotopy of a computable loop in such a manifold, showing that in general both of these properties are undecidable. This is joint work with Wesley Calvert.
Spectra of algebraic fields,
invited talk in the Special Session on Computability Theory
and Effective Algebra, at the AMS Sectional Meeting
(October 12, 2008; Wesleyan University, Middletown, CT.)
pdf download
Abstract: The spectrum of a structure is the set of all Turing degrees of presentations of that structure. We investigate the possible spectra of a field F algebraic over its prime field. In general these turn out to be of the form {d : T is c.e. in d}, for a specific set T of natural numbers which depends on F. Conversely, every set of this form, for any T, is the spectrum of some normal algebraic field. From the theory of enumeration degrees, it follows that every such field must have a jump degree. Another corollary is the known result that there is a normal algebraic field extension of the rationals with no least degree in its spectrum. This is joint work with Andrey Frolov and Iskander Kalimullin.
Degrees of categoricity of algebraic fields,
seminar talk in the MIT Logic Seminar
(October 1, 2008; Massachusetts Institute
of Technology, Cambridge, MA.)
pdf download
Abstract: Let F be a computable field: a countable field in which the addition and multiplication are given by computable functions. We investigate the Turing degrees d such that F is d-computably categorical, meaning that d is able to compute isomorphisms between F and any other computable field isomorphic to F. We prove that algebraic fields can fail to be 0'-computably categorical, but that there is a degree d, low relative to 0', such that every algebraic field is d-computably categorical. We also prove analogous results, one jump lower, for computable fields with splitting algorithms.
Local computability and uncountable structures,
seminar talk in the Connecticut Logic Seminar
(September 29, 2008; Wesleyan University, Middletown, CT)
pdf download
Abstract: Computable model theory has always restricted itself to the study of countable structures. The natural numbers form the standard domain and range for partial computable functions, due to the finiteness of the programs and computations in the Turing model. In this talk we continue to use this standard model of computation, but in such a way as to allow consideration of uncountable structures. We no longer aspire to describe a structure S globally. Instead, we content ourselves with a local description: a list of the finitely-generated substructures of S, up to isomorphism. Initially we require that these substructures should be computable, and that the list of them be given effectively. If this can be done, then S is said to be locally computable. (Such an S must have only countably many finitely-generated substructures, up to isomorphism.) Then we consider more sophisticated effective descriptions of S, by naming embeddings among the substructures which reflect the inclusions in S. We will prove several theorems about locally computable structures, but since the notion of local computability is extremely new, much of this talk will be devoted to definitions and examples.
Difficulty of factoring polynomials and finding roots,
seminar talk in the CUNY Logic Workshop
(September 12, 2008; CUNY Graduate Center, New York, NY.)
pdf download
Abstract: For a polynomial p(X) over a field F, two basic questions arise: whether p(X) factors over F, and whether p(X) has a root in F. Clearly these questions are related, and over a computable field F, they are known to be Turing-equivalent, by work of Frohlich and Shepherdson from 1956. As computability theorists, we sharpen the question by using the notion of an m-reduction: does there exist a computable total function g such that the n-th polynomial over F factors iff the g(n)-th polynomial over F has a root? And conversely? In this talk we will answer this question for algebraic fields, showing that in one direction an m-reduction (in fact a 1-reduction) always exists, but that in the other direction it may not exist. To find out which direction is which, come to the talk!
Local computability, from the First CUNY Workshop on
Effective Mathematics of the Uncountable
(August 20, 2008; CUNY Graduate Center, New York, NY.)
pdf download
Abstract: In local computability, we stick to the standard model of finite-time Turing computability, and attempt to describe an uncountable structure S by giving effective presentations of the finitely-generated substructures of S, up to isomorphism, and also describing, effectively, how those substructures fit together to form the entire structure S. We will describe several different extents to which we may be able to give such descriptions: for example, the field of complex numbers admits a very accurate description, while the field of real numbers only admits a much less accurate one, and the ordered field of real numbers is not locally computable at all, since it contains finitely-generated substructures with no computable presentation.We will present several theorems to support the argument that this method is a natural analogue to the usual notion of computability on countable structures. We will also compare it with the earlier notion of local constructivizability, devised by Ershov, and possibly to some of the other concepts presented in this workshop for effective mathematics on uncountable structures.
Automorphism spectra and tree-definability,
contributed talk at the European Summer Meeting of the
Association for Symbolic Logic
(July 3, 2008; University of Bern, Switzerland.)
pdf download
Abstract: The automorphism spectrum of a computable structure A is the set of Turing degrees of nontrivial automorphisms of A. Thus it measures the complexity of the symmetries of A. We present several results about which sets of Turing degrees can be automorphism spectra of computable structures, and in particular, for which single degrees d a computable structure can have automorphism spectrum {d}. This condition is equivalent to d being tree-definable, i.e. to the existence of a computable subtree T of omega^(< omega) such that there is exactly one path p through T and deg(p)=d. This is joint work with Valentina Harizanov and Andrei Morozov.
Perfect local computability and computable simulations,
contributed talk at the meeting
Computability in Europe
(June 18, 2008; University of Athens, Greece.)
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. This is joint work with Dustin Mulcahey.