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
Generic Muchnik Reducibility And Enumerations Of Ideals
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Abstract:
If A and B are countable structures, then A is Muchnik reducible to B if every ω-copy of B computes an ω-copy of A. This can be interpreted as saying that B is intrinsically at least as complicated as A. While this is a natural way to compare the complexity of structures, it was limited to the countable setting until Schweber introduced an extension to arbitrary structures: if A and B are (possibly uncountable) structures, then A is generically Muchnik reducible to B if in some (equivalently, any) forcing extension that makes A and B countable, A is Muchnik reducible to B.
Uri Andrews gave two talks in this seminar on generic Muchnik reducibility. I will cover earlier work; no memory of Uri’s talks will be assumed. We will discuss the fact that Cantor space is strictly below Baire space in the generic Muchnik degrees. On the other hand, Baire space is generic Muchnik equivalent to the field of reals, and in fact, any expansion of the reals by countably many continuous functions. On the other hand, if we expand Cantor space by adding jump and join, then we get a structure that is strictly more complicated than Baire space, one that is generic Muchnik above every Borel structure.
These results follow from facts about the complexity of enumerating the sets in countable Turing ideals. For example, in any countable Scott ideal, there is an enumeration of the sets that does not compute an enumeration of the infinite sets (or equivalently, of the functions in the ideal). In a countable jump ideal, every enumeration of the infinite sets computes an enumeration of the sets along with the jumps of joins of members of the list. On the other hand, it is not always possible to compute an enumeration along with jump and join as functions on indices.
This work is joint with Andrews, Knight, Kuyper, Lempp, and Soskova. It builds on work of Knight, Montalbán, and Schweber (2016); Igusa and Knight (2016); Igusa, Knight, and Schweber (2017); and Downey, Greenberg, and myself (2016).
Generic Muchnik Reducibility And Enumerations Of Ideals
| H.264 Video | 25489_29047_8676_Generic_Muchnik_Reducibility_and_Enumerations_of_Ideals.mp4 |