Non-deterministic computation and the Jayne-Rogers Theorem
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 applica...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2014-03-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1404.0079v1 |