diophantus

Log in | Create account
Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to hello@diophantus.org

pdf On the Kolmogorov-Chaitin Complexity for short sequences

Delahaye Jean-Paul, Zenil Hector
08 Apr 2007 cs.CC, cs.IT, math.IT arxiv.org/abs/0704.1043
Abstract. A drawback of Kolmogorov-Chaitin complexity (K) as a function from s to the shortest program producing s is its noncomputability which limits its range of applicability. Moreover, when strings are short, the dependence of K on a particular universal Turing machine U can be arbitrary. In practice one can approximate it by computable compression methods. However, such compression methods do not always provide meaningful approximations--for strings shorter, for example, than typical compiler lengths. In this paper we suggest an empirical approach to overcome this difficulty and to obtain a stable definition of the Kolmogorov-Chaitin complexity for short sequences. Additionally, a correlation in terms of distribution frequencies was found across the output of two models of abstract machines, namely unidimensional cellular automata and deterministic Turing machine.

Reviews

There are no reviews yet.


Comments

There are no comments yet.

Log in to leave a comment.


Reviews

There are no reviews yet.

Log in to leave a review.