Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Online/Virtual |
Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Generically Computable Structures
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Abstract:
We define notions of generically and coarsely computable and computably enumerable structures. There are two directions in which these notions could potentially trivialize: either all structures could have a densely computable copy or only those having a computable (or computably enumerable) copy. We show that particular classes of structures realize each of these extremal conditions, while other classes realize neither of them.
To further explore these concepts, we introduce a graded family of elementarity conditions for substructures, in which we require that the dense sets under consideration be a strong substructure of the original structure. Here, again, for a given class the notion could trivialize in the same two directions, and we show that both are possible. For each class we investigate, there is some n such that requiring Sigma_n-elementarity is enough to minimize the class of generically or densely computable structures, witnessing the essentially structural character of these notions.
No Notes/Supplements UploadedGenerically Computable Structures
| H.264 Video | 25184_28682_8542_Generically_Computable_Structures.mp4 |