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 selfdelimiting 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: Blankendmarker complexity, Chaitin (selfdelimiting) complexity, random strings.
Categories: G.3
