Effectivity and reducibility with ordinal Turing machines

Article type: Research Article

Authors: Carl, Merlin^{; *}

Affiliations: Institut für mathematische, naturwissenschaftliche und technische Bildung, Abteilung für Mathematik und ihre Didaktik, Europa-Universität Flensburg, Germany. merlin.carl@uni-flensburg.de

Correspondence: [*] Corresponding author. merlin.carl@uni-flensburg.de.

Abstract: This article expands our work in (LNCS 9709 (2016), 225–233). By its reliance on Turing computability, the classical theory of effectivity, along with effective reducibility and Weihrauch reducibility, is only applicable to objects that are either countable or can be encoded by countable objects. We propose a notion of effectivity based on Koepke’s Ordinal Turing Machines (OTMs) that applies to arbitrary set-theoretical Π2-statements, along with according variants of effective reducibility and Weihrauch reducibility. As a sample application, we compare various choice principles with respect to effectivity.

Keywords: Effective reducibility, ordinal computability

DOI: 10.3233/COM-210307

Journal: Computability, vol. 10, no. 4, pp. 289-304, 2021