# Blog Archives

# Topic Archive: computable model theory

# A Local Characterization of VC-minimality

(Work joint with Vincent Guingona.) I’ll talk about a problem in the intersection of computable model theory and classical model theory. The notion of VC-minimality, though intriguing, has proven very difficult to work with. It has even been difficult to check whether familiar examples are VC-minimal. This has led model theorists (chiefly my co-author) to ask whether there was a “local” (read “simpler”) characterization of VC-minimality. I suggested a computable model theoretic version of this question in terms of the index set of VC-minimality. We answered this question by giving a local characterization of VC-minimality, and we showed that VC-minimality is a Π^{0}_{4}-complete notion.

# Σ-Presentable structures over *HF(R)*

If we replace in the definition of computable structures the concept of classical computability over ω with Σ-definability over the structure ** HF(R)** (the hereditarily finite superstructure over the ordered field

**of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over**

*R***. This generalization could correspond to the hypothetical situation when we have an opportunity to use algorithms written in a powerful programming language with “real” reals, elements of**

*HF(R)***, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.**

*R*In the talk, a survey will be given of the results on the existence of Σ-presentations for various structures, on the number of non Σ-isomorphic presentations, and on the existence of Σ-parameterizations for classes of presentations.

# Computability, computational complexity and geometric group theory

The three topics in the title have been inextricably linked since the famous 1912 paper of Max Dehn. In recent years the asymptotic-generic point of view of geometric group theory has given rise to new areas of computability and computational complexity. I will discuss how this arose and then focus on one recent development in computability theory, namely, coarse computability and the coarse computability bound.

# Computable Functors between Nested Equivalence Structures and Full Trees of Finite Height

Trees have long been used throughout mathematics to better understand and represent many different types of objects and structures. In this talk we examine finitely nested equivalence structures. Such structures consist of a set of natural numbers and a finite number of equivalence relations which are nested inside of each other. (That is, their resulting equivalence classes are subsets of each other.) We utilize the notions of category theory to build functors between nested equivalence structures and full trees of finite height. These functors behave quite nicely, and we build them in a computable way so that the various computability-theoretic properties of the structures are preserved. We discuss computable isomorphisms and the Turing degree spectrum of a structure – defining and giving examples of each, and showing how, once our computable functors are constructed, such properties transfer readily between nested equivalence structures and trees.

# Lengths of roots of polynomials over *k((G))*

Mourgues and Ressayre showed that any real closed field $R$ can be mapped isomorphically onto a truncation-closed subfield of the Hahn field $k((G))$, where $G$ is the natural value group of $R$ and $k$ is the residue field. If we fix a section of the residue field and a well ordering < of $R$, then the procedure of Mourgues and Ressayre yields a canonical section of $G$ and a unique embedding $d: R$ → $k((G))$. Julia Knight and I believed we had shown that for a real closed field $R$ with a well ordering < of type ω, the series in $d(R)$ have length less than ω^{ωω}, but we found a mistake in our proof. We needed a better understanding of what happens to lengths under root-taking. In this talk, we give a partial answer, which allows us to prove the original statement and generalize it. We make use of unpublished notes of Starchenko on the Newton-Puiseux method for taking roots of polynomials.

# Computable functors and effective interpretations

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.

Recent joint work by Harrison-Trainor, Melnikov, Montalbán, and the speaker has established that computable functors are closely connected to Montalban’s notion of *effective interpretation* of one class **C** of countable structures in another class **D**. We will explain the connections and discuss the extent to which they realize the model-theorist’s suspicion that functors are really just another version of interpretations.

# The degree spectra of orders on a computable Abelian group

For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π^{0}_{1} class. However, not all Π^{0}_{1} classes can occur in this way, and we investigate the possible Turing degrees of their members. First, we describe the connection between orders for a group and bases for the group. Additionally, we extend a previously known result regarding the Turing degrees not represented in the space of orders of some group.

# Low for omega and equivalence class isomorphism properties

We look at the property of being low for isomorphism, restricted to certain classes of structures – if *C* is a class of structures, a set *D* is low for *C* isomorphism iff for any two structures in *C*, if *D* computes an isomorphism between them then there is a computable isomorphism between them. In particular we will show that exactly those sets which cannot compute non-zero Δ_{2} degrees are low for ω-isomorphism (when ω is viewed purely as an order), and we will show that no set which computes a non-zero Δ_{2} set or which computes a separating set for any two computably inseparable c.e. degrees is low for equivalence class isomorphism.

# Computability theoretic properties of isomorphisms between partial computable injection structures

A partial computable injection structure consists of a computable set of natural numbers and a partial computable, injective (1-1) function. Clearly, the isomorphism type of such a structure is determined by the kinds and number of orbits of the elements under the function application. First, we investigate partial computable injection structures always having computable isomorphisms to other isomorphic structures, and we analyze what goes wrong in structures without such computable isomorphisms. Additionally, we do the same for partial computable injection structures under Δ_{2}-isomorphisms and Δ_{3}-isomorphisms.

# NERDS

The Autumn 2014 meeting of NERDS, the New England Recursion & Definability Seminar, will take place on Saturday, October 18 at Assumption College, in Worcester, MA, beginning at 10:30 a.m. The principal organizers are Brooke Andersen, Damir Dzhafarov, and Reed Solomon. All talks are posted on nylogic.org (find NERDS under the “Conferences” tab), and they will take place in the Carriage House building on the campus of Assumption College. Directions.

# Computable algebra: a personal perspective

I will give a brief overview of some of my recent research in the field of Computable Algebra, emphasizing connections between Computability Theory and Algebra. Some of the topics that I hope to cover include Artinian and Euclidean rings, as well as infinite dimensional vector spaces. There will be no proofs, just statements of theorems along with discussions on their logical and algebraic significance.

# Generalizing Turing machines: $\omega_1$-computation

While Turing machines are well established as the principal framework for theoretical computation on the natural numbers, no machine model for computation on uncountable domains has achieved any similarly dominant status. We will give an overview of various methods that have been explored, including computable analysis, the Blum-Shub-Smale model of computation on the real numbers, local computability, α-recursion theory, and certain models of computation over ordinal time (one of which turns out to be equivalent to α-recursion). Each of these has strengths and weaknesses, for which reason no one of them has come to dominate the discussion. Much of the talk will be expository, describing these different notions of computation, but we will finish with a specific example from ω_{1}-recursive model theory which shows how phenomena that were unknown under Turing computation on ω can arise in the context of ω_{1}-computable model theory.

# Quasiminimality and computability

We briefly define computability on uncountable domains via Σ_{1}-recursion, with an emphasis on ω_{1}-computability. We will then apply this notion of uncountable computability to quasiminimal excellent classes. We will concentrate on the pseudo-exponential fields and the topological group covers of the complex numbers. We show that the group covers are relatively ω_{1}-computably categorical while the pseudo-exponential fields are not even ω_{1}-computably categorical.