Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 1 / Issue 1

available in:   HTML (40 kB) PDF (237 kB) PS (65 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-001-01-0048


What Is a Random String?

Cristian S. Calude (Computer Science Department, University of Auckland, New Zealand)

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.

Categories: G.3