Below are links to pdf files of the slides from various talks I have given recently.

*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 ofand 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.Q

*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 structureBin another oneAyields a homomorphism from the automorphism groupAut(A)intoAut(B). Indeed, it yields a functor from the categoryIso(A)of all isomorphic copies ofA(under isomorphisms) into the categoryIso(B). In traditional model theory, the converse is false. However, when we extend the concept of interpretation to allow interpretations byLformulas, we find that now the converse essentially holds: every Borel functor arises from an infinitary interpretation of_{ω1ω}BinA, and likewise every Borel-measurable homomorphism fromAut(A)intoAut(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 ringR, Hilbert's Tenth Problem is the setHTP(R)of polynomialsp ∈ R[X_1,X_2, . . . ]with solutions inR. We consider computability of this set for subringsRof the fieldQof rational numbers. Applying Baire category theory to these subrings, which naturally form a topological space, relates their setsHTP(R)to the setHTP(, whose decidability remains an open question. The main result is that, for an arbitrary setQ)C,HTP(computesQ)Cif and only if the subringsRfor whichHTP(R)computesCform a nonmeager class. Similar results hold for 1-reducibility, for admitting a Diophantine model ofZ, and for existential definability ofZ.

*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 ringR, Hilbert's Tenth Problem is the setHTP(R), of polynomialsp ∈ R[X_1,X_2, . . . ]for whichp=0has a solution inR. In 1970, Matiyasevich completed work of Davis, Putnam, and Robinson, giving a 1-reduction from the Halting Problem toHTP(. We show that this method can succeed only on a measure-0 meager subclass of the class of all subrings ofZ)Q, because the class of thoseRfor which the jump_{W}W'does not 1-reduce toHTP(Rhas measure 1. (Here_{W})Ris the subring in which just the primes in_{W}Whave inverses. The usual measure on Cantor space is transferred to the class of all subrings ofQusing 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 orderL, there exists a real closed field whose spectrum is the pre-image under jump of the spectrum ofL. 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 ringR, Hilbert's Tenth ProblemHTP(R)is the set of those polynomialspinR[Xfor which_{1},X_{2}, . . . ]p=0has a solution inR. In 1970, Matiyasevich completed work of Davis, Putnam, and Robinson, showing thatHTP(ℤ)is undecidable and in fact has Turing degree. The Turing degree of0'HTP(ℚ)remains unknown.We will discuss the state of knowledge about

HTP(R)whenRis a subring ofℚ. A recent result of Eisenträger, Park, Shlapentokh, and the speaker shows that every computably enumerable Turing degree between the degrees ofHTP(ℚ)andHTP(ℤ)can be realized as the degree ofHTP(R)for such a subringR, and indeed thatRcan 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 theoryDCF. 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._{0}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 interpretationis 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 ofcomputable functorwhich 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 fieldF, we consider two fundamental questions about polynomialspinF[X]. First, which ones have proper factorizations inF[X]? And second, which ones have roots inF? Clearly these questions are related, and initially it may seem that the first one is easier: whenphas degree > 3, finding a factorization appears easier than finding a root. However, by the same token, it should then be harder to show thatphas no factorization than it is to show thatphas 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 fieldF(that is, a countable field in which the field operations can be computed by a Turing machine), we first describeTuring 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 anm-reduction. Allm-reductions are Turing reductions, but not vice versa, and we will see thatm-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 categoriesandCwhose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functorDFfromtoCshould be effective: given a structureDMfromas an oracle, it should compute the structureCF(M)in, and given aD-morphismCgfromMtoNas an oracle, it should compute the-morphismDF(g)fromF(M)toF(N). Moreover, one would hope forFto be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for anFto 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 structureMis the set of all Turing degrees of structures isomorphic toM. 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 graphsG, under the jump operation. To establish this, we describe the proofs of two theorems: one showing how to build the appropriate differential fieldKfrom a given graphG, and the other showing that every low model of the theoryDCF_{0}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 low_{4}case does not hold forDCF_{0}.

*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 graphG, we build a countable fieldF(G), uniformly effectively from an arbitrary presentation ofG. There is a uniform effective method of recovering the graphGfrom the fieldF(G). Moreover, each isomorphismgfromGonto anyG'may be turned into an isomorphismF(g)fromF(G)ontoF(G'), again by a uniform effective method so thatF(g)is computable fromg. Likewise, an isomorphismffromF(G)onto anyF(G')may be turned back into an isomorphismgwithF(g)=f. Not every fieldFisomorphic toF(G)is actually of the formF(G'), but for every suchF, there is a graphG'isomorphic toGand an isomorphismffromFontoF(G'), both computable inF.It follows that many computable-model-theoretic properties which hold of some graph

Gwill carry over to the fieldF(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 fieldF =. Two notions of basis are relevant. An independent set generatingQ(X_{1},X_{2}, . . . )Gis known as abasisfor the group, while an independent set generating the fieldFis called apure transcendence basis. In fields, the termtranscendence basisdenotes any maximal independent set, whether or not it generatesF; the analogous notion forGis 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 ofFandG. ForF, 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 ofGto 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 forG, every computable presentation has aΠbasis, and that this bound is sharp, whereas for fields, many questions about the Turing degrees of pure transcendence bases remain open._{2}^{0}

*Degrees of categoricity of algebraic fields,*
from the Penn State University Logic Seminar
(20 March 2012).

pdf download

Abstract:LetFbe a computable field: a countable field in which the addition and multiplication are given by computable functions. We investigate the Turing degreesdsuch thatFisd-computably categorical, meaning thatdis able to compute isomorphisms betweenFand every other computable field isomorphic toF. We prove that algebraic fields can fail to be0'-computably categorical, but that there is a degreed, low relative to0', such that every algebraic field isd-computably categorical. We also prove analogous results, one jump lower, for computable fieldsFfor which the irreducibility of polynomials inF[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 structureAiscomputably categoricalif every computable structureBclassically isomorphic toAis in fact computably isomorphic toA. 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 isalgebraicif it is an algebraic extension of its prime subfield.) It follows that there exists a computably categorical algebraic fieldFfor which the more general property of relative computable categoricity fails. ThisFis 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 than1is 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 fieldsF, the second half of Rabin's Theorem says that this subfield is Turing-equivalent to the set of irreducible polynomials inF[X]. We investigate possible extensions of this second half, asking both about the degree of the differential fieldKwithin its differential closure and about the degree of the set of constraints forK, which forms the closest analogue to the set of irreducible polynomials. 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 degree0; it remains open whether the same holds for low-5 degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebraB. For such subalgebrasA, we show that it is possible for the spectrum of the unary relationAonBto contain a low-5 degree without containing0. That is,Ais a low-5 Boolean subalgebra ofB, butBhas no computable Boolean subalgebraCwith (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 degree0; it remains open whether the same holds for low-5 degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebraB. For such subalgebrasA, we show that it is possible for the spectrum of the unary relationAonBto contain a low-5 degree without containing0.

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-nand Non-low-nDegrees,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 structureAiscomputably categoricalif for every computableBclassically isomorphic toA, there exists a computable isomorphism fromAontoB. 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 fieldFwith a splitting algorithm, i.e. such that the set of irreducible polynomials inF[X]is computable. We prove that such a field is computably categorical if and only if its orbit relationG= {(a,b) : there existshin Aut(F)withh(a)=b} is computable. WithFalgebraic, the orbit relationGcan also be defined by an AE-formula in the language of fields. Ostensibly, the condition given above is therefore Sigma-4, but sinceFis assumed to have a splitting algorithm, computability ofGis 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 fieldsFand embeddings ofFinto 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 inF[X], the set of polynomials there with roots inF, and the different waysFcan sit within computable presentations of its algebraic closure. We also examine this issue for noncomputable fields, considering the spectrum of the fieldFand 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 problemHin BSS-computation to be BSS-reducible to a countable set. Intuitively, it seems that a countable set ought not to contain enough information to decide membership in a reasonably complex (uncountable) set such asH. We confirm this intuition, and prove a more general theorem linking the cardinality of the oracle set to the cardinality, in a local sense, of the set which it computes. We also mention other recent results on BSS-computation and algebraic real numbers.

*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 setA(d)of algebraic numbers of degree at mostdis not decidable inA(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 eachxinRas 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 domainR^n, unlike standard Turing machines, which can search through omega^n. We exploit this difference to show that for polynomials inR[X], although factorizability is (easily) BSS-decidable, there are no BSS algorithms for finding the factors, nor for determining roots inRorC. We also give a (significantly more involved) proof that the set of algebraic real numbers of degreed+1over the rationals is not BSS-decidable from an oracle for the set of algebraic reals of degree less than or equal tod. 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 everyn, both the class of high-nTuring degrees and the class of non-low-nTuring 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 extensionFof 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 ofFin 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 structureFand computability whenFis 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 fieldFwhich has infinite transcendence degree over the rationalsQ, yet is computably categorical. The key is to be able to enumerate an image of the original transcendence basis in every computable copyF'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 inQ, and results from algebraic geometry further restrict the possible solutions, to the point that the solutions we do find inF'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 fieldFalgebraic over its prime field. In general these turn out to be of the form {d:Tis c.e. ind}, for a specific setTof natural numbers which depends onF. Conversely, every set of this form, for anyT, 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:LetFbe a computable field: a countable field in which the addition and multiplication are given by computable functions. We investigate the Turing degreesdsuch thatFisd-computably categorical, meaning thatdis able to compute isomorphisms betweenFand any other computable field isomorphic toF. We prove that algebraic fields can fail to be0'-computably categorical, but that there is a degreed, low relative to0', such that every algebraic field isd-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 structureSglobally. Instead, we content ourselves with a local description: a list of the finitely-generated substructures ofS, 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, thenSis said to be locally computable. (Such anSmust have only countably many finitely-generated substructures, up to isomorphism.) Then we consider more sophisticated effective descriptions ofS, by naming embeddings among the substructures which reflect the inclusions inS. 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 polynomialp(X)over a fieldF, two basic questions arise: whetherp(X)factors overF, and whetherp(X)has a root inF. Clearly these questions are related, and over a computable fieldF, 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 anm-reduction: does there exist a computable total functiongsuch that then-th polynomial overFfactors iff theg(n)-th polynomial overFhas a root? And conversely? In this talk we will answer this question for algebraic fields, showing that in one direction anm-reduction (in fact a1-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 structureSby giving effective presentations of the finitely-generated substructures ofS, up to isomorphism, and also describing, effectively, how those substructures fit together to form the entire structureS. 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:Theautomorphism spectrumof a computable structureAis the set of Turing degrees of nontrivial automorphisms ofA. Thus it measures the complexity of the symmetries ofA. We present several results about which sets of Turing degrees can be automorphism spectra of computable structures, and in particular, for which single degreesda computable structure can have automorphism spectrum {d}. This condition is equivalent todbeingtree-definable, i.e. to the existence of a computable subtreeTofωsuch that there is exactly one path^{< ω}pthroughTand 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) structuresSthat have highly effective presentations of their local properties. We show that every suchScan 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 ofS, examining its connections to the category of all finitely generated substructures ofS. This is joint work with Dustin Mulcahey.