Effective Complexity and its Relation to Logical Depth

Details Effective Complexity and its Relation to Logical Depth Effective Complexity and its Relation to Logical Depth

2008-10-31

arxiv.org/abs/0810.5663v1

IEEE Trans. Inf. Th., Vol. 56/9 pp. 4593-4607 (2010)

Computer Science

Information Theory

14 pages, 2 figures

Scientific paper

10.1109/TIT.2010.2053892

Effective complexity measures the information content of the regularities of an object. It has been introduced by M. Gell-Mann and S. Lloyd to avoid some of the disadvantages of Kolmogorov complexity, also known as algorithmic information content. In this paper, we give a precise formal definition of effective complexity and rigorous proofs of its basic properties. In particular, we show that incompressible binary strings are effectively simple, and we prove the existence of strings that have effective complexity close to their lengths. Furthermore, we show that effective complexity is related to Bennett's logical depth: If the effective complexity of a string $x$ exceeds a certain explicit threshold then that string must have astronomically large depth; otherwise, the depth can be arbitrarily small.

Affiliated with

Also associated with

No associations

Rating

Effective Complexity and its Relation to Logical Depth 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 Effective Complexity and its Relation to Logical Depth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Effective Complexity and its Relation to Logical Depth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-456909