ABSTRACT. This talk discusses work in progress on using a Cobham-style recursion on sets to define an analogue of polynomial time computation on sets. We define a new # (smash) function which operates on sets, along with a natural notion of embedding, and use these to define Cobham-style bounded \epsilon-recursive definitions of functions that operate on sets. This gives a natural method of defining set-valued functions with feasible computational complexity; in particular, it gives a characterization of polynomial time in terms of computation on hereditarily finite sets.

This extends prior work of Beckmann-Buss-Friedman and Arai, who introduced safe-normal \epsilon-recursion

This talk discusses joint work with A. Beckmann, S. Friedman, M. Mueller, and N. Thapen.

ABSTRACT. We take a look on the development on the questions around infinitely deep languages that has happened during the last 40 years.

ABSTRACT. For the field of real numbers, we have the usual floor function, with range equal to the set of integers. If we expand the reals, adding the function 2^x, then for a positive integer x, 2^x is also a positive integer. Mourgues and Ressayre showed that every real closed field has an ``integer part''. The construction is complicated, not arithmetical, but hyperarithmetical. Ressayre showed that every real closed exponential field has an ``exponential integer part''. This construction is even more complicated. It may not finish in the least admissible set over the input.

ABSTRACT. We describe a uniform family {T_n} of complete, first order theories for n\ge 1, each in a countable language, such that each T_n has an atomic model of size aleph_n, every atomic model of size aleph_n is maximal, and hence has no atomic model of size aleph_{n+1}. Moreover, the class of atomic models satisfies disjoint amalgamation in aleph_k for every k

The negative results all follow from general observations about locally finite closure relations, while the positive results follow by an inductive argument akin to Shelah's work on identifying excellent classes.

This is joint work with John Baldwin and Martin Koerwien.

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.

ABSTRACT. We say that a theory $T$ is intermediate under effective reducibility if the isomorphism problems among its computable models is neither hyperarithmetic nor on top under effective reducibility. We exhibit partial results towards showing that the existence of such theories is equivalent to the negation of Vaught's conjecture.

We prove that if an infinitary sentence $T$ is uniformly effectively dense, a property we define in the paper, then no extension of it is intermediate, at least when relativized to every oracle in a cone. As an application we show that no infinitary sentence whose models are all linear orderings is intermediate under effective reducibility relative to every oracle in a cone.