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

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.