Logic Seminar
Siddharth Bhaskar
IU Bloomington
Recursion over abstract structures
Abstract: There are various ways to define the notion of a computable function or predicate over an arbitrary first-order structure. For example, we may specify some model of computation, such as a register machine or system of recursive programs, or we might encode elements of the structure by natural numbers and say that a function is computable when it lifts to a recursive function over N. Given a notion of computability, we can then ask how similar the recursion theory of our structure is to classical recursion theory over N. For example: do we have recursive pairing and unpairing functions? Do we have a Godel numbering and a corresponding evaluation function? Can we compute every recursive function with a tail recursion?
We will survey the general picture and focus on the case most dissimilar from the classical one: namely, functions computable by recursive programs over locally finite structures, where the answers to the above questions tend to be negative. We shall show that for several such structures, computability corresponds to classical complexity classes. We shall finish with a case study of computability over the algebraic closure of a finite field of characteristic p, as well as some open questions.
Thursday March 17, 2016 at 4:00 PM in SEO 427