LIPIcs.STACS.2017.17.pdf
- Filesize: 0.54 MB
- 14 pages
Document
Monte Carlo Computability
Authors
-
Part of:
Volume:
34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-03-06
Cite AsGet BibTex
Vasco Brattka, Rupert Hölzl, and Rutger Kuyper. Monte Carlo Computability. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.17
https://doi.org/10.4230/LIPIcs.STACS.2017.17
Abstract
We introduce Monte Carlo computability as a probabilistic concept of computability on infinite objects and prove that Monte Carlo computable functions are closed under composition. We then mutually separate the following classes of functions from each other: the class of multi-valued functions that are non-deterministically computable, that of Las Vegas computable functions, and that of Monte Carlo computable functions. We give natural examples of computational problems witnessing these separations. As a specific problem which is Monte Carlo computable but neither Las Vegas computable nor non-deterministically computable, we study the problem of sorting infinite sequences that was recently introduced by Neumann and Pauly. Their results allow us to draw conclusions about the relation between algebraic models and Monte Carlo computability.
Keywords
- Weihrauch degrees
- Weak Weak Konig's Lemma
- Monte Carlo computability
- algorithmic randomness
- sorting
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads