The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent collapses cases confounding all distinct degrees of randomness and pseudo-randomness, here we take into consideration the generative mechanism of the systems considered in the ensemble to separate objects that may comply with the principle under some restriction and whose entropy is maximal but may be generated recursively from those that are actually algorithmically random offering a refinement to classical Maxent. We take advantage of a causal algorithmic calculus to derive a thermodynamic-like result based on how difficult it is to reprogram a computer code. Using the distinction between computable and algorithmic randomness, we quantify the cost in information loss associated with reprogramming. To illustrate this, we apply the algorithmic refinement to Maxent on graphs and introduce a Maximal Algorithmic Randomness Preferential Attachment (MARPA) Algorithm, a generalisation over previous approaches. We discuss practical implications of evaluation of network randomness. Our analysis provides insight in that the reprogrammability asymmetry appears to originate from a non-monotonic relationship to algorithmic probability. Our analysis motivates further analysis of the origin and consequences of the aforementioned asymmetries, reprogrammability, and computation.
Other examples combining computation and entropy can be found in Seth Lloyd's concept of @cite_21 , heavily indebted to the work of Kolmogorov and Chaitin and to Bennett's notion of @cite_37 ; in Baez's @cite_45 approach that is capable of defining an algorithmic version of and , and in Crutchfield's using @cite_17 . Zurek has also proposed the inclusion of algorithmic randomness in a definition of physical entropy to allow the reformulation of aspects of thermodynamics, such as the Maxwell demon's thought experiment @cite_39 @cite_18 .
@cite_37 @cite_18 @cite_21 @cite_39 @cite_45 @cite_17
2281664623 2024802184 1981700764 2010954373 106879616 2065533060
Some mathematical and natural objects (a random sequence, a sequence of zeros, a perfect crystal, a gas) are intuitively trivial, while others (e.g. the human body, the digits of π) contain internal evidence of a nontrivial causal history. We formalize this distinction by defining an object’s “logical depth” as the time required by a standard universal Turing machine to generate it from an input that is algorithmically random (i.e. Martin-Lof random). This definition of depth is shown to be reasonably machineindependent, as well as obeying a slow-growth law: deep objects cannot be quickly produced from shallow ones by any deterministic process, nor with much probability by a probabilistic process, but can be produced slowly. Next we apply depth to the physical problem of “self-organization,” inquiring in particular under what conditions (e.g. noise, irreversibility, spatial and other symmetries of the initial conditions and equations of motion) statistical-mechanical model systems can imitate computers well enough to undergo unbounded increase of depth in the limit of infinite space and time. Algorithmic complexity is a measure of randomness. In contrast to Shannon's entropy it is defined without a recourse to probabilities; for a binary string s it is given by the size, in bits, of the shortest computer program with the output s. I show that algorithmic complexity sets limits on the thermodynamic cost of computations, casts a new light on the limitations of Maxwell's demon and can be used to define distance between binary strings. Abstract A measure of complexity for the macroscopic states of physical systems is defined. Called depth, the measure is universal: it applies to all physical systems. The form of the measure is uniquely fixed by the requirement that it be a continuous, additive function of the processes that can result in a state. Applied to a Hamiltonian system, the measure is equal to the difference between the system's coarse- and fine-grained entropy, a quantity that we call thermodynamic depth. The measure satisfies the intuitive requirements that wholly ordered and wholly random systems are not thermodynamically deep and that a complex object together with a copy is not much deeper than the object alone. Applied to systems capable of computation, the measure yields a conventional computational measure of complexity as a special case. The relation of depth and thermodynamic depth to previously proposed definitions of complexity is discussed, and applications to physical, chemical, and mathematical problems are proposed. ital Algorithmic ital randomness provides a rigorous, entropylike measure of disorder of an individual, microscopic, definite state of a physical system. It is defined by the size (in binary digits) of the shortest message specifying the microstate uniquely up to the assumed resolution. Equivalently, algorithmic randomness can be expressed as the number of bits in the smallest program for a universal computer that can reproduce the state in question (for instance, by plotting it with the assumed accuracy). In contrast to the traditional definitions of entropy, algorithmic randomness can be used to measure disorder without any recourse to probabilities. Algorithmic randomness is typically very difficult to calculate exactly but relatively easy to estimate. In large systems, probabilistic ensemble definitions of entropy (e.g., coarse-grained entropy of Gibbs and Boltzmann's entropy ital H =ln ital W , as well as Shannon's information-theoretic entropy) provide accurate estimates of the algorithmic entropy of an individual system or its average value for an ensemble. One is thus able to rederive much of thermodynamics and statistical mechanics in a setting very different from the usual. ital Physical ital entropy , I suggest, is a sum of (i) the missing information measured by Shannon's formula and (ii) of the algorithmic informationmore » content---algorithmic randomness---present in the available data about the system. This definition of entropy is essential in describing the operation of thermodynamic engines from the viewpoint of information gathering and using systems. These Maxwell demon-type entities are capable of acquiring and processing information and therefore can decide'' on the basis of the results of their measurements and computations the best strategy for extracting energy from their surroundings. From their internal point of view the outcome of each measurement is definite.« less Thermodynamic depth is an appealing but flawed structural complexity measure. It depends on a set of macroscopic states for a system, but neither its original introduction by Lloyd and Pagels nor any follow-up work has considered how to select these states. Depth, therefore, is at root arbitrary. Computational mechanics, an alternative approach to structural complexity, provides a definition for a system close_quote s minimal, necessary causal states and a procedure for finding them. We show that the rate of increase in thermodynamic depth, or ital dive , is the system close_quote s reverse-time Shannon entropy rate, and so depth only measures degrees of macroscopic randomness, not structure. To fix this, we redefine the depth in terms of the causal state representation emdash epsilon -machines emdash and show that this representation gives the minimum dive consistent with accurate prediction. Thus, epsilon -machines are optimally shallow. copyright ital 1999 ital The American Physical Society