University Seminar: Logic Across Disciplines-Computability via definability and polynomial computability

Title: Computability via definability and polynomial computability
Speaker:  Sergei Goncharov, Russian Academy of Sciences
Date and Time: Wednesday, February 6, 3:45-4:45PM
Place: Rome Hall (801 22nd Street), Room 771

Abstract:  Computability on abstract models can be based on definability via Delta _0 and Sigma formulas. We introduce computability over an abstract model M based on definability over hereditary finite subset superstructure over M or hereditary finite list-extension over M. We will consider different enrichments of our language for the notion of terms and discuss the problem of complexity of definable functions. It is a basis for constructing a logic programming language. We will construct extensions with different properties of computability.