Is Randomness "Native" to Computer Science?

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We survey the Kolmogorov's approach to the notion of randomness through the Kolmogorov complexity theory. The original motivation of Kolmogorov was to give up a quantitative definition of information. In this theory, an object is randomness in the sense that it has a large information content. Afterwards, we present parts of the work of Martin-Lof, Schnorr, Chaitin and Levin which supply a mathematical notion of randomness throughout diverse theories from the the 60' up to recently.
43 pages

Keywords

Logic, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/145156

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0801.0289
 http://arxiv.org/abs/0801.0289
 Current Trends in Theoretical Computer Science. Vol2, World Scientific (Ed.) (2004) 141-180

Collections

arXiv