Real Computable Manifolds and Homotopy Groups,
from the Eighth Conference on Unconventional Computation
(September 10, 2009; Universidade dos Acores,
Punta 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.