Friday, March 13, 201512:30 pmnote new timeCUNY Logic WorkshopGC 6417

Σ-Presentable structures over HF(R)

Andrey Morozov

Sobolev Institute of Mathematics, Novosibirsk State University

Andrey Morozov

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.

There will be two Logic Workshop talks today: this one, at 12:30, and another one at 2:00, by Sergei Starchenko.

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.