The characterization of Weihrauch reducibility in systems containing E-PA^{\omega} + QF-AC^{0,0}

DOI10.1017/JSL.2020.53MaRDI QIDQ6337659arXivFDO

Authors Patrick Uftring

Publication date 30 March 2020

Mathematics Subject Classification ID

Proof-theoretic aspects of linear logic and other substructural logics (03F52) Higher-type and set recursion theory (03D65) Other degrees and reducibilities in computability and recursion theory (03D30)

Abstract: We characterize Weihrauch reducibility in E-PA${}^{omega}$ + QF-AC${}^{0,0}$ and all systems containing it by the provability in a linear variant of the same calculus using modifications of G"odel's Dialectica interpretation that incorporate ideas from linear logic, nonstandard arithmetic, higher-order computability, and phase semantics.

This page was built for publication: The characterization of Weihrauch reducibility in systems containing E-PA$^{\omega}$ + QF-AC$^{0,0}$

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