Classification and Measure for Algebraic Fields,
invited talk in the Cornell Logic Seminar
(August 23, 2017; Cornell University, Ithaca, NY).
pdf download
Abstract: The algebraic fields of characteristic 0 are precisely the subfields of the algebraic closure of the rationals, up to isomorphism. We describe a way to classify them effectively, via a computable homeomorphism onto Cantor space. This homeomorphism makes it natural to transfer Lebesgue measure from Cantor space onto the class of these fields, but there is another probability measure on the same class which seems in some ways more natural than Lebesgue measure. We will discuss how certain properties of these fields -- notably, relative computable categoricity -- interact with these measures: the basic result is that only measure-0 many of these fields fail to be relatively computably categorical.
Computable Transformations of Structures,
invited special-session talk at the meeting Computability in Europe
(June 12, 2017; Turku, Finland).
pdf download
Abstract: We examine notions of computable reducibility on classes of countable structures. By using Turing functionals to define computable reductions, we may go beyond computable structures and consider broader classes of countable structures. We use these ideas to give effective classifications of the class of all algebraic field extensions of Q and of the class of all infinite finite-branching trees. With the notion of a computable homeomorphism (which is stronger than having a computable reduction in both directions), we can use these classifications to put measures on the spaces of structures and to define properties such as randomness for them.
Genericity, Infinitary Interpretations, and Automorphism Groups of Structures, invited talk at the Southeastern Logic Symposium (March 5, 2017; University of Florida, Gainesville, FL.) pdf download
Abstract: It has long been recognized that the existence of an interpretation of one countable structure B in another one A yields a homomorphism from the automorphism group Aut(A) into Aut(B). Indeed, it yields a functor from the category Iso(A) of all isomorphic copies of A (under isomorphisms) into the category Iso(B). In traditional model theory, the converse is false. However, when we extend the concept of interpretation to allow interpretations by Lω1ω formulas, we find that now the converse essentially holds: every Borel functor arises from an infinitary interpretation of B in A, and likewise every Borel-measurable homomorphism from Aut(A) into Aut(B) arises from such an interpretation. Moreover, the complexity of an interpretation matches the complexities of the corresponding functor and homomorphism. We will discuss the concepts and the forcing necessary to prove these results and other corollaries. This is joint work with Matthew Harrison-Trainor and Antonio Montalban.
Baire Category for Hilbert's Tenth Problem Inside Q,
contributed talk at the meeting Computability in Europe
(June 27, 2016; Paris, France.)
pdf download
Abstract: For a ring R, Hilbert's Tenth Problem is the set HTP(R) of polynomials p ∈ R[X_1,X_2, . . . ] with solutions in R. We consider computability of this set for subrings R of the field Q of rational numbers. 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.
Hilbert's Tenth Problem for subrings of the rationals,
invited talk in the Special Session on Computability Theory and Applications,
at the AMS Sectional Meeting
(October 4, 2015; Chicago, IL.)
pdf download
Abstract: For a ring R, Hilbert's Tenth Problem is the set HTP(R), of polynomials p ∈ R[X_1,X_2, . . . ] for which p=0 has a solution in R. In 1970, Matiyasevich completed work of Davis, Putnam, and Robinson, giving a 1-reduction from the Halting Problem to HTP(Z). We show that this method can succeed only on a measure-0 meager subclass of the class of all subrings of Q, because the class of those RW for which the jump W' does not 1-reduce to HTP(RW) has measure 1. (Here RW is the subring in which just the primes in W have inverses. The usual measure on Cantor space is transferred to the class of all subrings of Q using this correspondence.) The proof uses a theorems from the work of Jockusch and from the Ph.D. thesis of his student Stuart Kurtz.
Degree spectra of real closed fields,
invited talk in the Model Theory Seminar,
CUNY Graduate Center
(11 September 2015).
pdf download
Abstract: The degree spectrum of a countable structure is the set of all Turing degrees of isomorphic copies of that structure. This topic has been widely studied in computable model theory. Here we examine the possible degree spectra of real closed fields, finding them to offer far more complexity than the related theory of algebraically closed fields. The co-author of this project, Victor Ocasio Gonzalez, showed in his dissertation that, for every linear order L, there exists a real closed field whose spectrum is the pre-image under jump of the spectrum of L. We add further results, distinguishing the cases of archimedean and non-archimedean real closed fields, and splitting the latter into two subcases based on the existence of a least multiplicative class of positive nonstandard elements. If such a class exists, then finiteness in the field is always decidable, but the case with no such class proves more interesting.
Hilbert's Tenth Problem for subrings of the rationals,
invited talk at the Institute for Mathematical Sciences, National University of Singapore, as part of the program Sets and Computations
(22 April 2015).
pdf download
Abstract: For an arbitrary ring R, Hilbert's Tenth Problem HTP(R) is the set of those polynomials p in R[X1,X2, . . . ] for which p=0 has a solution in R. In 1970, Matiyasevich completed work of Davis, Putnam, and Robinson, showing that HTP(ℤ) is undecidable and in fact has Turing degree 0'. The Turing degree of HTP(ℚ) remains unknown.We will discuss the state of knowledge about HTP(R) when R is a subring of ℚ. A recent result of Eisenträger, Park, Shlapentokh, and the speaker shows that every computably enumerable Turing degree between the degrees of HTP(ℚ) and HTP(ℤ) can be realized as the degree of HTP(R) for such a subring R, and indeed that R can be taken to be computably presentable. We will also consider questions about the possible asymptotic densities within ℚ of such subrings, and about the extent to which these methods can be extended to other subrings.
Functors and effective interpretations in model theory,
invited talk at the annual North American meeting of the Association for Symbolic Logic, University of Illinois Urbana-Champaign
(27 March 2015).
pdf download
Abstract: We present and connect several recent results in computable model theory in which one class of countable structures is coded into another class. These include a coding of countable graphs into fields, by Park, Poonen, Schoutens, Shlapentokh, and the speaker, which is quantifiably more effective than the well-known Friedman-Stanley coding and which shows that fields have the same completeness properties as graphs in regard to Turing degree spectra and computable categoricity. Additionally, we will describe Ocasio's version of Marker's coding of linear orders into real closed fields, followed by a recent coding of graphs into differentially closed fields using the ENI-DOP for the theory DCF0. Both of these are seen to be somewhat less effective, although they are still Turing-computable embeddings, in the sense defined by Knight and her many co-authors.To a model theorist, the map from graphs into fields will be readily recognizable as an interpretation, using existential formulas. The other two maps can also be seen as interpretations, but require the use of computable infinitary ∃∀ formulas. Montalbán's definition of effective interpretation is relevant here. On the other hand, the map from graphs into fields can be viewed as a kind of functor, since it codes each graph into a field in such a way that the isomorphisms between any two graphs give rise (in an effective way) to all isomorphisms between the corresponding fields. We will state the natural definition of computable functor which arose, along with its generalization to the other two maps. Finally, we will describe work by Harrison-Trainor, Melnikov, Montalbán, and the author in which these two notions (along with the longstanding notion of Σ-definability, used mostly in Novosibirsk) are all shown to be equivalent.
Computability theory at work: factoring polynomials
and finding roots,
invited talk at the MAA MathFest, Portland, OR
(7 August 2014).
pdf download
Abstract: Given a field F, we consider two fundamental questions about polynomials p in F[X]. First, which ones have proper factorizations in F[X]? And second, which ones have roots in F? Clearly these questions are related, and initially it may seem that the first one is easier: when p has degree > 3, finding a factorization appears easier than finding a root. However, by the same token, it should then be harder to show that p has no factorization than it is to show that p has no root. So the basic intuitions do not suggest how to compare the difficulty of these questions. The point of this talk is to show how computability theory (a.k.a. recursion theory) allows us to address the problem of deciding which of these two questions is more difficult. Working in a computable field F (that is, a countable field in which the field operations can be computed by a Turing machine), we first describe Turing reductions, using the above two questions as an illustration. Each question turns out to be Turing-reducible to the other, meaning that, by this measure, they have the same level of difficulty. However, we also describe the very natural notion of an m-reduction. All m-reductions are Turing reductions, but not vice versa, and we will see that m-reducibility definitively establishes which of the two questions is more difficult.
Functors in computable model theory,
in the Infinity Workshop, Kurt Gödel Research Center, Vienna, Austria
(10 July 2014).
pdf download
Abstract: We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories C and D whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor F from C to D should be effective: given a structure M from C as an oracle, it should compute the structure F(M) in D, and given a C-morphism g from M to N as an oracle, it should compute the D-morphism F(g) from F(M) to F(N). Moreover, one would hope for F to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an F to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.
Degree spectra of differentially closed fields,
in the Berkeley Recursion Theory Seminar
(14 April 2014).
pdf download
Abstract: The spectrum Spec(M) of a countable structure M is the set of all Turing degrees of structures isomorphic to M. This topic has been the focus of much research. Here we describe joint work by Dave Marker and the speaker on the spectra of countable differentially closed fields of characteristic 0: they are precisely the preimages { d : d' ∈ Spec(G) } of spectra of arbitrary countable graphs G, under the jump operation. To establish this, we describe the proofs of two theorems: one showing how to build the appropriate differential field K from a given graph G, and the other showing that every low model of the theory DCF0 is isomorphic to a computable one. The latter theorem (which relativizes, to give the main result above) resembles the famous result of Downey and Jockusch on Boolean algebras, but the proof is different, yielding a Δ2 isomorphism between the low model and its computable copy; moreover, our first theorem shows that the extension of the Boolean-algebra result to the low4 case does not hold for DCF0.
The theory of fields is complete for isomorphisms,
invited talk in the Computable Model Theory workshop
at the Banff International Research Station
(7 November 2013).
pdf download
video of this talk
Abstract: We give a highly effective coding of countable graphs into countable fields. For each countable graph G, we build a countable field F(G), uniformly effectively from an arbitrary presentation of G. There is a uniform effective method of recovering the graph G from the field F(G). Moreover, each isomorphism g from G onto any G' may be turned into an isomorphism F(g) from F(G) onto F(G'), again by a uniform effective method so that F(g) is computable from g. Likewise, an isomorphism f from F(G) onto any F(G') may be turned back into an isomorphism g with F(g)=f. Not every field F isomorphic to F(G) is actually of the form F(G'), but for every such F, there is a graph G' isomorphic to G and an isomorphism f from F onto F(G'), both computable in F.It follows that many computable-model-theoretic properties which hold of some graph G will carry over to the field F(G), including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph. By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.
This work is joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh.
Independent sets in free groups and fields,
from the Rutgers Logic Seminar
(18 February 2013, Rutgers University, New Brunswick, NJ).
pdf download
Abstract: There is a strong analogy between the free group G on countably many generators and the purely transcendental field F = Q(X1,X2, . . . ). Two notions of basis are relevant. An independent set generating G is known as a basis for the group, while an independent set generating the field F is called a pure transcendence basis. In fields, the term transcendence basis denotes any maximal independent set, whether or not it generates F; the analogous notion for G is less common, and we simply call it a maximal independent set. In joint work, Charles McCoy and I have established various effectiveness properties of these notions in computable presentations of F and G. For F, the Turing degrees of transcendence bases form an upper cone above the degree of the dependence relation, which is always computably enumerable. In contrast, it is possible for a computable copy of G to have a computable maximal independent set, yet to have noncomputable dependence relation. When one considers independent generating sets, the situation changes: work of McCoy and Wallbaum established that for G, every computable presentation has a Π20 basis, and that this bound is sharp, whereas for fields, many questions about the Turing degrees of pure transcendence bases remain open.
Degrees of categoricity of algebraic fields,
from the Penn State University Logic Seminar
(20 March 2012).
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 every 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 F for which the irreducibility of polynomials in F[X] is decidable.
Computable differential fields,
invited talk at the Computability Theory week
(February 10, 2012; Mathematisches Forschungsinstitut Oberwolfach, Germany.)
pdf download
Abstract: We present 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. This is joint work with Alexey Ovchinnikov and Dmitry Trushin. Also see the summary of this talk written for the report on the computability week at Oberwolfach.
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 ω< ω 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.