2013 seminar talk: Universal functions over locally finite structures
Talk held by Asylkhan Khisamiev (Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences) at the KGRC seminar on 2013-11-28.
Abstract
Now it is generally accepted that one of the important generalizations of the concept of computability is $\Sigma$-definability (generalized computability) in admissible sets. This generalization has made possible to study computability problems over arbitrary structures, for instance, over the field of real numbers. A crucial result of classical computability theory is the existence of an universal partially computable function. It is known that an universal $\Sigma$-predicate exists in every admissible set, but this is false for $\Sigma$-functions. Therefore, it is interesting to know which conditions on $\mathfrak{M}$ guarantee the existence of an universal $\Sigma$-function in the hereditarily finite admissible set $\mathbb{HF}(\mathfrak{M})$ over $\mathfrak{M}$. In this talk we discuss the problem of the existence of an universal $\Sigma$-function in the hereditarily finite admissible set over some locally finite structures.