JUCS - Journal of Universal Computer Science 1(1): 48-66, doi: 10.3217/jucs-001-01-0048
What Is a Random String?
expand article infoCristian S. S. Calude‡
‡ University of Auckland, Auckland, New Zealand

Corresponding author: Cristian S. Calude ( cristian@cs.auckland.ac.nz )

© Cristian S. Calude.
This article is freely available under the J.UCS Open Content License.
Citation: Calude CSS (1995) What Is a Random String? JUCS - Journal of Universal Computer Science 1(1): 48-66. https://doi.org/10.3217/jucs-001-01-0048
Open Access
Abstract
Chaitin s algorithmic definition of random strings - based on the complexity induced by self-delimiting computers - is critically discussed. One shows that Chaitin s model satisfy many natural requirements related to randomness, so it can be considered as an adequate model for finite random objects. It is a better model than the original (Kolmogorov) proposal. Finally, some open problems will be discussed.
Keywords
Blank-endmarker complexity, Chaitin (self-delimiting) complexity, random strings.