About


Schedule


Directions
All talks are scheduled for forty-five (45) minutes in the Sea-Tac Room of the Hyatt Regency O'Hare. The Sea-Tac Room is on the ground floor of the hotel just past and to the right of the escalators up to the hotel check-in desks.

A light breakfast (coffee, assorted pastries, and fruit yogurts) will be available in or near the Sea-Tac Room at the indicated times.

Saturday 12 May 2012

  9:30: Breakfast
10:30: Harizanov: Structures, Theories, and Diagrams
11:30: Stukachev: On Processes and Structures
  2:30: Kalimullin: Reducibilities for the Families of Computably Enumerable Sets
  3:30: Andrews: Recursive Spectra of Strongly Minimal Theories Satisfying the Zilber Trichotomy
  4:30: Puzarenko: Computability on Admissible Structures: Applications to Classical Computability

Sunday 13 May 2012

  9:00: Breakfast
10:30: McCoy: Describing Free Groups
11:30: Soskov: What Should Be a Jump Inversion of a Structure?
  2:30: Miller: Automorphism Groups of Computable Structures
  3:30: Soskova: Enumeration Degree Spectra
  4:30: Frolov: Computable Linear Orderings. Coding Theorems.

Andrews: Recursive Spectra of Strongly Minimal Theories Satisfying the Zilber Trichotomy

Abstract: (Joint with Alice Medvedev) We conjecture that for a strongly minimal theory T in a finite signature satisfying the Zilber Trichotomy, there are only three possibilities for the recursive spectrum of T: all countable models of T are recursively presentable; none of them are recursively presentable; or only the zero-dimensional model of T is recursively presentable.

Via an analysis of which definable sets are recursive in recursive strongly minimal disintegrated structures and modular groups, we prove this conjecture for disintegrated theories and for modular groups. The conjecture also holds via known results for fields. The conjecture remains open for finite covers of groups and fields.


Frolov: Computable Linear Orderings. Coding Theorems.

Abstract: R. Downey and J. Knight proved that a linear ordering L has an X'-computable copy iff (η+2+η)·L has an X-computable copy. Φ is called a 0(n)-coding functional if L has an X(n)-computable copy iff Φ(L) has an X-computable copy for any linear ordering L. So, Φ(L) = (η+2+η)·L is a 0'-coding functional. If Φ be a 0(n)-coding functional, then the following theorem is called a 0(n)-coding theorem.

Theorem: For any linear ordering L, L has an X(n)-computable copy iff Φ(L) has an X-computable copy.

At first, we have a nice property. Namely, if Φn is a 0(n)-coding functional and Φm is a 0(m)-coding functional, then Φn º Φm is a 0n+m-coding functional.

At second, we have the connection between coding functionals and low linear orderings. Let Φn be a 0(n)-coding functional. If L = Φn(L') for some L', then L has a copy in x∈Δ02 iff x is Δ02 non-lown.

The main results are the following theorems and their corollaries.

Theorem: Let τ be an x-computable linear ordering with the first and the last elements. If L is an x'-computable linear ordering, then τ·L has an x-computable copy.

It follows from the theorem that (η+2+η)·L, (η+1+2+···+k+1+η)·L, and many others are 0'-coding functionals.

Theorem: Let τ be an x-computable linear ordering with x-computable successor relation such that
(∀ x) (∀ n) (∃ x',y') [ (x <τ x' <τ y') & |[x',y']|τ = n ]
and
(∀ x) (∀ n) (∃ x',y') [ (x >τ x' >τ y') & |[x',y']|τ = n ].
If L is an x'-computable linear ordering, then τ·L has an x-computable copy with x-computable successor relation.

It follows from both the previous theorems that ζ·L, (ζ+1+ζ+2+ζ+···)·L, (ω*+η+ζ)·L and many others are 0''-coding functionals.

We remark that earlier R. Watnick proved that ζ·L is a 0''-coding functional using the infinite injury priority method. Now, we prove the same using only the finite-injury priority method.


Harizanov: Structures, Theories, and Diagrams

Abstract: We consider structures for computable languages and with computable domains. Such a structure is computable if its atomic diagram is decidable, and the structure is decidable if its elementary diagram is decidable. An equivalence structure is a structure with a single equivalence relation. An injection structure is a structure with a single one-to-one function.

For equivalence structures and injection structures, we explore the connection between the complexity of their characters and their first-order theories. We show that if an equivalence structure has a computable character, then there is a decidable structure isomorphic to it. As a corollary, we obtain that every computably categorical equivalence structure is decidable. We also show that for an injection structure with a computable character, there is a decidable structure isomorphic to it. However, there are computably categorical injection structures with undecidable theories.

This is joint work with Doug Cenzer and Jeff Remmel.


Kalimullin: Reducibilities for the Families of Computably Enumerable Sets

Abstract: Relationships between different reducibilities of families will be studied with the Σ-reducibility based on the Σ-definability relation of admissible sets as a stongest version and with the Muchnik reducibility as a weakest. For the Muchnik reducibility we will see how every countable distributive lattice can be embedded using a coding of numberings of Δ02 sets into the Wehner style families.


McCoy: Describing Free Groups

This talk examines how hard it is to describe, with computable infinitary sentences, each countable free group (up to isomorphism) and how hard it is to describe free groups in a way that distinguishes them from other groups. Injury arguments are used to establish that the defining sentence is as simple as possible (in regard to its syntactic complexity). In a number of cases, the simplest defining sentence is definitely not the most ``obvious'' or most ``natural,'' and, more importantly, the injury argument itself suggested at what level to search for the simplest defining sentence. In the most difficult case, the injury arguments led the authors to a question about free groups that had only recently been resolved. These facts precisely demonstrate ways in which computability constructions can inform the studies of definability and algebraic structure.

Joint work with J. Carson, V. Harizanov, J. Knight, K. Lange, A. Morozov, S. Quinn, C. Safranski, J. Wallbaum.


Miller: Automorphism Groups of Computable Structures

Abstract: We present basic definitions and results on the presentation of the automorphism group of a computable structure. This group often has size continuum, so the standard notion of a computable group is not relevant. Instead, we offer two definitions, one weak and one strong, of type-2 computable presentability for such groups. All computable structures S have automorphism groups presentable under the weak definition, but presentability under the strong definition requires that the full orbit relation RS be computably enumerable:

RS = { (a0 ,...,an,b0 ,...,bn) : (∃σ∈Aut(S))(∀i≤n) σ(ai )=bi }

We offer nascent results and observations regarding these concepts. The basic definitions, while absolutely natural, have only recently been developed, and one reason for presenting them here is to encourage work on them among the conference participants.


Puzarenko: Computability on Admissible Structures: Applications to Classical Computability

Abstract: The following aspects are discussed: the existence of a fixed point for the jump operator, categorical computable structures with certain properties, reducibilities on admissibles (on structures) and on structures.


Soskov: What Should Be a Jump Inversion of a Structure?

Abstract: In his recent paper Rice Sequences of Relations, Antonio Montalban gives a survey of several approaches to the definition of the notion of the jump of a structure A. Though based on different ideas, all these definitions share a common feature. Namely, the subsets of |A| definable by computable Σ2 formulae on A coincide with the sets definable on the jump of A by means of computable Σ1 formulae.

In our talk we shall concentrate on the reverse problem. Given a structure A above 0(n) with n ≥ 1, how to define a structure M such that the subsets of |A| definable by means of computable Σ1 formulae on A coincide with the sets definable on M by means of computable Σn+1 formulae. We shall show that Marker's extensions introduced by Goncharov and Khoussainov provide a general construction that solves the problem for all finite ordinals n and that in the general case such kind of jump inversions are impossible for infinite recursive ordinals.


Soskova: Enumeration Degree Spectra

Abstract: We will discuss two versions of the enumeration degree spectrum DS(A) of a countable structure A: the set of all enumeration degrees of the presentations of A by all total enumerations and by all partial enumerations of A. The co-spectrum of A is the set of all lower bounds of DS(A).

We will consider the connections between the degree spectrum and the co-spectrum of A in both cases. The normal form of the elements of the co-spectrum of A will help us to see that the co-spectrum of A is the same in the total and the partial case. We will present some properties of the co-spectra as variants of Selman's theorem, the minimal pair theorem and quasi-minimal degree theorem for degree spectra. We will show that the degree spectrum of A has a degree if and only if it has a countable base. We will discuss a generalized Jump inversion theorem for degree spectra and some applications of it.


Stukachev: On Processes and Structures

Abstract: We introduce an approach to generalized computability which allows to formulate and prove in a general setting most of the known results in effective model theory and gives tools sufficient to obtain some new results. We present examples of both kinds and state some open questions.