Σ-Presentable structures over HF(R)
Sobolev Institute of Mathematics, Novosibirsk State University
If we replace in the definition of computable structures the concept of classical computability over ω with Σ-definability over the structure HF(R) (the hereditarily finite superstructure over the ordered field R of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over HF(R). This generalization could correspond to the hypothetical situation when we have an opportunity to use algorithms written in a powerful programming language with “real” reals, elements of R, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.
In the talk, a survey will be given of the results on the existence of Σ-presentations for various structures, on the number of non Σ-isomorphic presentations, and on the existence of Σ-parameterizations for classes of presentations.
Prof. Andrey Morozov received his doctorate in 1983, as a student of Sergey Goncharov at Novosibirsk State University, Russia. Since then he has risen to serve as Head of the Laboratory of Logical Systems at Novosibirsk, and has held assorted visiting positions in other countries during that time as well. He studies computability theory, with a focus on Sigma-definability and computable model theory.