Effective Complexity and its Relation to Logical Depth TeX Export

@article{citeulike:3474992, abstract = {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.}, archivePrefix = {arXiv}, author = {{Ay}, N. and {Mueller}, M. and {Szkola}, A.}, citeulike-article-id = {3474992}, citeulike-linkout-0 = {http://arxiv.org/abs/0810.5663}, citeulike-linkout-1 = {http://arxiv.org/pdf/0810.5663}, citeulike-linkout-2 = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2008arXiv0810.5663A}, day = {31}, eprint = {0810.5663}, journal = {ArXiv e-prints}, keywords = {complexity, effective}, month = {October}, posted-at = {2009-09-30 15:47:27}, priority = {3}, title = {Effective Complexity and its Relation to Logical Depth}, url = {http://arxiv.org/abs/0810.5663}, year = {2008} }

TY - JOUR ID - citeulike:3474992 L3 - citeulike-article-id:3474992 N2 - 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. JF - ArXiv e-prints TI - Effective Complexity and its Relation to Logical Depth KW - complexity KW - effective AU - {Ay}, N AU - {Mueller}, M AU - {Szkola}, A PY - 2008/October/31/ UR - http://arxiv.org/abs/0810.5663 ER -