An application of Martin-Löf randomness to effective probability theory

Mathieu Hoyrup, Cristóbal Rojas

Resultado de la investigación: Conference contribution

22 Citas (Scopus)

Resumen

In this paper we provide a framework for computable analysis of measure, probability and integration theories. We work on computable metric spaces with computable Borel probability measures. We introduce and study the framework of layerwise computability which lies on Martin-Löf randomness and the existence of a universal randomness test. We then prove characterizations of effective notions of measurability and integrability in terms of layerwise computability. On the one hand it gives a simple way of handling effective measure theory, on the other hand it provides powerful tools to study Martin-Löf randomness, as illustrated in a sequel paper.

Idioma originalEnglish
Título de la publicación alojadaMathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings
Páginas260-269
Número de páginas10
Volumen5635 LNCS
DOI
EstadoPublished - 2009
Evento5th Conference on Computability in Europe, CiE 2009 - Heidelberg, Germany
Duración: 19 jul 200924 jul 2009

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen5635 LNCS
ISSN (versión impresa)03029743
ISSN (versión digital)16113349

Other

Other5th Conference on Computability in Europe, CiE 2009
PaísGermany
CiudadHeidelberg
Período19/07/0924/07/09

Huella dactilar

Probability Theory
Randomness
Computability
Probability Measure
Computable Analysis
Measure Theory
Measurability
Borel Measure
Integrability
Metric space
Framework

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Citar esto

Hoyrup, M., & Rojas, C. (2009). An application of Martin-Löf randomness to effective probability theory. En Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings (Vol. 5635 LNCS, pp. 260-269). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5635 LNCS). https://doi.org/10.1007/978-3-642-03073-4_27
Hoyrup, Mathieu ; Rojas, Cristóbal. / An application of Martin-Löf randomness to effective probability theory. Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings. Vol. 5635 LNCS 2009. pp. 260-269 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{570874687be646858e6072a49c8ce52b,
title = "An application of Martin-L{\"o}f randomness to effective probability theory",
abstract = "In this paper we provide a framework for computable analysis of measure, probability and integration theories. We work on computable metric spaces with computable Borel probability measures. We introduce and study the framework of layerwise computability which lies on Martin-L{\"o}f randomness and the existence of a universal randomness test. We then prove characterizations of effective notions of measurability and integrability in terms of layerwise computability. On the one hand it gives a simple way of handling effective measure theory, on the other hand it provides powerful tools to study Martin-L{\"o}f randomness, as illustrated in a sequel paper.",
keywords = "Algorithmic randomness, Computable analysis, Effective probability theory, Layerwise computability, Lebesgue integration, Universal test",
author = "Mathieu Hoyrup and Crist{\'o}bal Rojas",
year = "2009",
doi = "10.1007/978-3-642-03073-4_27",
language = "English",
isbn = "3642030726",
volume = "5635 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "260--269",
booktitle = "Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings",

}

Hoyrup, M & Rojas, C 2009, An application of Martin-Löf randomness to effective probability theory. En Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings. vol. 5635 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5635 LNCS, pp. 260-269, 5th Conference on Computability in Europe, CiE 2009, Heidelberg, Germany, 19/07/09. https://doi.org/10.1007/978-3-642-03073-4_27

An application of Martin-Löf randomness to effective probability theory. / Hoyrup, Mathieu; Rojas, Cristóbal.

Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings. Vol. 5635 LNCS 2009. p. 260-269 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5635 LNCS).

Resultado de la investigación: Conference contribution

TY - GEN

T1 - An application of Martin-Löf randomness to effective probability theory

AU - Hoyrup, Mathieu

AU - Rojas, Cristóbal

PY - 2009

Y1 - 2009

N2 - In this paper we provide a framework for computable analysis of measure, probability and integration theories. We work on computable metric spaces with computable Borel probability measures. We introduce and study the framework of layerwise computability which lies on Martin-Löf randomness and the existence of a universal randomness test. We then prove characterizations of effective notions of measurability and integrability in terms of layerwise computability. On the one hand it gives a simple way of handling effective measure theory, on the other hand it provides powerful tools to study Martin-Löf randomness, as illustrated in a sequel paper.

AB - In this paper we provide a framework for computable analysis of measure, probability and integration theories. We work on computable metric spaces with computable Borel probability measures. We introduce and study the framework of layerwise computability which lies on Martin-Löf randomness and the existence of a universal randomness test. We then prove characterizations of effective notions of measurability and integrability in terms of layerwise computability. On the one hand it gives a simple way of handling effective measure theory, on the other hand it provides powerful tools to study Martin-Löf randomness, as illustrated in a sequel paper.

KW - Algorithmic randomness

KW - Computable analysis

KW - Effective probability theory

KW - Layerwise computability

KW - Lebesgue integration

KW - Universal test

UR - http://www.scopus.com/inward/record.url?scp=76249104926&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03073-4_27

DO - 10.1007/978-3-642-03073-4_27

M3 - Conference contribution

AN - SCOPUS:76249104926

SN - 3642030726

SN - 9783642030727

VL - 5635 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 260

EP - 269

BT - Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings

ER -

Hoyrup M, Rojas C. An application of Martin-Löf randomness to effective probability theory. En Mathematical Theory and Computational Practice - 5th Conference on Computability in Europe, CiE 2009, Proceedings. Vol. 5635 LNCS. 2009. p. 260-269. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-03073-4_27