Effectivity and Reducibility with Ordinal Turing Machines
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917506638151680 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | This article expands our work in [Ca16]. 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.
We also propose a generalization to set-theoretical formulas of arbitrary quantifier complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1811_11630 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Effectivity and Reducibility with Ordinal Turing Machines Carl, Merlin Logic This article expands our work in [Ca16]. 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. We also propose a generalization to set-theoretical formulas of arbitrary quantifier complexity. |
| title | Effectivity and Reducibility with Ordinal Turing Machines |
| topic | Logic |
| url | https://arxiv.org/abs/1811.11630 |