The speaker for this week's seminar is Patrick Uftring from the University of Munich. He will talk about Computable transformations of Turing degrees.
Abstract:
Following a conjecture by Vasco Brattka, we present a new result that fully characterizes all partial, multi-valued functions on the Turing degrees that have computable realizers. To be precise, for any such function f mappping n-many Turing degrees to a single Turing degree, there is a subset N of n such that for any degrees a_0, ..., a_n-1, the join of all degrees a_i with i in N is always a solution of f(a_0, ..., a_n-1). This yields short proofs of established results such as [2, Proposition 11.5] but also answers open questions such as "Are two applications of PA reducible to a single instance?" (private communication with Vasco Brattka, cf. [1, Proposition 38]). We also present an infinitary variant, which can e.g. be applied to Weihrauch reductions involving infinite suborders of Turing degrees and answers [1, Conjecture 37].
[1] Vasco Brattka, Loops, Inverse Limits and Non-Determinism, arXiv:2501.17734, pp. 1–18.
[2] Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer, On the Uniform Computational Content of Computability Theory, Theory of Computing Systems, vol. 61 (2017), no. 4, pp. 1376–1426.
