Non-deterministic computation and the Jayne-Rogers Theorem

Arno Pauly
Matthew de Brecht

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 Benedikt Löwe and Glynn Winskel: Proceedings 8th International Workshop on Developments in Computational Models (DCM 2012), Cambridge, United Kingdom, 17 June 2012, Electronic Proceedings in Theoretical Computer Science 143, pp. 87–96.
Published: 29th March 2014.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: