Date and Time: Wednesday, February 1st 4-5 p.m.
Place: Rome 206
Speaker: Philip White, GWU
Title: The Syntactic Characterization of Computability Theoretic Properties.
Abstract: The study of computable structure theory took off in the 1970s with parallel developments happening independently in both the East and West. In the West, the first results were for particular algebraic structures. For example: Every r.e. presented vector space has a dependence algorithm if and only if it has an r.e. basis (Metakides-Nerode 1977). The thought arises: is there a metatheorem for arbitrary computable structures for this type of result? On the one hand you have computability theoretic properties, and on the other hand you have a structure with designated operations and constants -- it is natural to ask "how are they related?" The way computable structure theory was developed in the East made it particularly suited for metatheorems of this type. For example: A decidable structure A has the property that every other decidable model classically isomorphic to A is recursively isomorphic to A iff there are a0,...,an in A for which (A, a0,...,an ) is a prime model and the atoms in the full Lindenbaum algebras of Th(A, a0,...,an) are uniformly r.e. (Nurtazin 1975). The first major metatheorem to emerge in the West was the Ash-Nerode theorem (1981), although similar precursors were known in the East. The Ash-Nerode theorem connects the computability theoretic property of "not r.e." to definability within an arbitrary computable structure. Since the original Ash-Nerode result for "not r.e." Other computability theoretic properties have been syntactically characterized, specifically immune and hyperimmune. The talk aims to survey this very fascinating area of logic!