License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.17
URN: urn:nbn:de:0030-drops-70164
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7016/
Go to the corresponding LIPIcs Volume Portal

Brattka, Vasco ; Hölzl, Rupert ; Kuyper, Rutger

Monte Carlo Computability

pdf-format:
LIPIcs-STACS-2017-17.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{brattka_et_al:LIPIcs:2017:7016,
  author =	{Vasco Brattka and Rupert H{\"o}lzl and Rutger Kuyper},
  title =	{{Monte Carlo Computability}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7016},
  URN =		{urn:nbn:de:0030-drops-70164},
  doi =		{10.4230/LIPIcs.STACS.2017.17},
  annote =	{Keywords: Weihrauch degrees, Weak Weak Konig's Lemma, Monte Carlo computability, algorithmic randomness, sorting}
}

Keywords: Weihrauch degrees, Weak Weak Konig's Lemma, Monte Carlo computability, algorithmic randomness, sorting
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI