Ordinal Reductions on Choice Principles
Jasper Stammes

Abstract:
In classical computability theory and computable analysis, two problems’ relative computability can be studied through several notions of reducibility. We wish to generalize a few of these notions. Instead of using a classical Turing machine, we consider a model of computation that can handle objects of any cardinality.
The Ordinal Turing Machine (OTM) is a generalization of the classical Turing machine, where computations have unbounded available time and space. In this thesis we will study the relative OTM-computability of construction problems arising from choice principles in set theory, based on similar work by Carl. We will use two existing notions of reducibility: OTM-reductions and ordinal Weihrauch reductions. We also define two similar reductions. In this setting, we prove the first known non-trivial case of OTM-irreducibility.