On the Kolmogorov-Chaitin Complexity for short sequences

Details On the Kolmogorov-Chaitin Complexity for short sequences On the Kolmogorov-Chaitin Complexity for short sequences

2007-04-08

arxiv.org/abs/0704.1043v5

Computer Science

Computational Complexity

21 pages. Paper webpage: http://www.mathrix.org/experimentalAIT/

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Kolmogorov-Chaitin Complexity for short sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Kolmogorov-Chaitin Complexity for short sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Kolmogorov-Chaitin Complexity for short sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386970