Monte Carlo Computability

Authors Vasco Brattka, Rupert Hölzl, Rutger Kuyper



PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.17.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Vasco Brattka
Rupert Hölzl
Rutger Kuyper

Cite As Get 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

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.

Subject Classification

Keywords
  • Weihrauch degrees
  • Weak Weak Konig's Lemma
  • Monte Carlo computability
  • algorithmic randomness
  • sorting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail