Towards a stable definition of program-size complexity

Abstract

We propose a test based on the theory of algorithmic complexity and an experimental evaluation of Levin's universal distribution to identify evidence in support of or in contravention of the claim that the world is algorithmic in nature. To this end statistical comparisons are undertaken of the frequency distributions of data from physical sources--repositories of information such as images, data stored in a hard drive, computer programs and DNA sequences--and the output frequency distributions generated by purely algorithmic means--by running abstract computing devices such as Turing machines, cellular automata and Post Tag systems. Statistical correlations were found and their significance measured

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

Similar books and articles

Complexity: hierarchical structures and scaling in physics.R. Badii - 1997 - New York: Cambridge University Press. Edited by A. Politi.
Super Turing-machines.Jack Copeland - 1998 - Complexity 4 (1):30-32.
Cellular automata.Francesco Berto & Jacopo Tagliabue - 2012 - Stanford Encyclopedia of Philosophy.
Is Evolution Algorithmic?Marcin Miłkowski - 2009 - Minds and Machines 19 (4):465-475.
Algorithmic randomness in empirical data.James W. McAllister - 2003 - Studies in History and Philosophy of Science Part A 34 (3):633-646.
What is a complex system?James Ladyman, James Lambert & Karoline Wiesner - 2013 - European Journal for Philosophy of Science 3 (1):33-67.

Analytics

Added to PP
2013-04-07

Downloads
17 (#738,490)

6 months
2 (#658,848)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references