Non-deterministic computation and the Jayne-Rogers Theorem

2014/04/01 by Arno Pauly, Matthew de Brecht
Computer Science · Mathematics · #cs.LO #math.LO

paper · pdf · doi:10.4204/eptcs.143.8

published as EPTCS 143, 2014, pp. 87-96 · In Proceedings DCM 2012, arXiv:1403.7579

arxiv created 2014/04/01 · arxiv updated 2014/04/02

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.

Citations

• Proceedings 8th International Workshop on Developments in Computational Models