Non-deterministic computation and the Jayne-Rogers theorem

MaRDI QIDQ4994845zbMATH OpenFDO

Authors Arno Pauly, Matthew De Brecht

Publication date 22 June 2021

Full work available at URL https://arxiv.org/abs/1404.0079, http://eptcs.web.cse.unsw.edu.au/paper.cgi?DCM2012.8

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Computation over the reals, computable analysis (03D78) Descriptive set theory (03E15)

Abstract: We provide a simple proof of a computable analogue to the Jayne Rogers Theorem from descriptive set theory. The difficulty of the proof is delegated to a simulation result pertaining to non-deterministic type-2 machines. Thus, we demonstrate that developments in computational models can have applications in fields thought to be far removed from it.

Recommendations

• Classical computability and indicators of nondeterminism
• Some observations on `A new proof of a theorem of Jayne and Rogers'
• From nonstandard analysis to various flavours of computability theory
• New Computational Paradigms

Cited in

(11)

• Comparing representations for function spaces in computable analysis
• A topological view on algebraic computation models
• Universality, optimality, and randomness deficiency
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
• A Galois connection between Turing jumps and limits
• A comparison of concepts from computable analysis and effective descriptive set theory
• Computability of Subsets of Metric Spaces
• Weihrauch Complexity in Computable Analysis
• Point Degree Spectra of Represented Spaces
• The Dyck and the Preiss separation uniformly

This page was built for publication: Non-deterministic computation and the Jayne-Rogers theorem

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