Chapter 12: The Principle of Computational Equivalence

Section 6: Computational Irreducibility

Amount of computation [and computational irreducibility]

Computational irreducibility suggests that it might be possible to define "amount of computation" as an independently meaningful quantity—perhaps vaguely like entropy or amount of information. And such a quantity might satisfy laws vaguely analogous to the laws of thermodynamics that would for example determine what processes are possible and what are not. If one knew the fundamental rules for the universe then one way in principle to define the amount of computation associated with a given process would be to find the minimum number of applications of the rules for the universe that are needed to reproduce the process at some level of description.

From Stephen Wolfram: A New Kind of Science [citation]