Non-deterministic computation and the Jayne-Rogers Theorem

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.

In Proceedings DCM 2012, arXiv:1403.7579

References in corpus (11)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Effective Choice and Boundedness Principles in Computable Analysis
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• The degree structure of Weihrauch-reducibility
• Real Hypercomputation and Continuity
• On the (semi)lattices induced by continuous reducibilities
• Revising Type-2 Computation and Degrees of Discontinuity
• Computation with Advice
• Turing machines on represented sets, a model of computation for Analysis
• Infinite Oracle Queries in Type-2 Machines (Extended Abstract)

Cited by in corpus (8)

• A comparison of concepts from computable analysis and effective descriptive set theory
• Finite choice, convex choice and finding roots
• Weihrauch-completeness for layerwise computability
• A Galois connection between Turing jumps and limits
• Decomposing Borel functions using the Shore-Slaman join theorem
• Computability on the space of countable ordinals
• Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions
• A recursion theoretic foundation of computation over real numbers