Generalized effective reducibility

DOI10.1007/978-3-319-40189-8_23MaRDI QIDQ3188260zbMATH OpenOpenAlexFDO

Authors Merlin Carl

Publication date 17 August 2016

Published in Pursuit of the Universal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.01899

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Other degrees and reducibilities in computability and recursion theory (03D30) Axiom of choice and related propositions (03E25) Consistency and independence results (03E35)

Abstract: We introduce two notions of effective reducibility for set-theoretical statements, based on computability with Ordinal Turing Machines (OTMs), one of which resembles Turing reducibility while the other is modelled after Weihrauch reducibility. We give sample applications by showing that certain (algebraic) constructions are not effective in the OTM-sense and considerung the effective equivalence of various versions of the axiom of choice.

Recommendations

• Effectivity and reducibility with ordinal Turing machines
• Weihrauch degrees, omniscience principles and weak computability
• Turing Computations On Ordinals
• scientific article; zbMATH DE number 5049507
• Ordinal computations

Cites work

• Infinite time Turing machines
• On notions of computability-theoretic reduction between Π21 principles
• On the Effectivity of Some Field Constructions
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Turing Computations On Ordinals
• What is the theory ZFC without power set?

Cited in

(7)

• Towards computable analysis on the generalised real line
• scientific article; zbMATH DE number 1337728 (Why is no real title available?)
• Weihrauch Complexity in Computable Analysis
• Effectivity and reducibility with ordinal Turing machines
• Algebra and Coalgebra in Computer Science
• Polynomial-time axioms of choice and polynomial-time cardinality
• Full generalized effective reducibility

This page was built for publication: Generalized effective reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188260)