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.
Previous work has considered the question of replacing all or part of the statistical machinery from statistical mechanics in order to arrive at an algorithmic approach to thermodynamics. Some authors have discussed the analogy between algorithms and entropy @cite_6 @cite_2 . One example is the thought experiment Maxwell's demon'--whereby Maxwell suggested that the second law of thermodynamics might hypothetically be violated by introducing intelligence in the form of a being capable of following an algorithm that enabled it to distinguish between particles of high and low energy--taken together with Szilard's discussion of this paradox @cite_16 . Here we offer an alternative framework in terms of which Maxwell's paradox and other thermodynamic-like phenomena can be reformulated in terms of computer programs via algorithmic probability and program-size complexity.
@cite_16 @cite_6 @cite_2
1975892318 1487340131 2132219316
In memory of Leo Szilard, who passed away on May 30,1964, we present an English translation of his classical paper ober die Enfropieuerminderung in einem thermodynamischen System bei Eingrifen intelligenter Wesen, which appeared in the Zeitschrift fur Physik, 1929,53,840-856. The publication in this journal of this translation was approved by Dr. Szilard before he died, but he never saw the copy. At Mrs. Szilard's request, Dr. Carl Eckart revised the translation. This is one of the earliest, if not the earliest paper, in which the relations of physical entropy to information (in the sense of modem mathematical theory of communication) were rigorously demonstrated and in which Maxwell's famous demon was successfully exorcised: a milestone in the integration of physical and cognitive concepts. We compare the elementary theories of Shannon information and Kolmogorov complexity, the extent to which they have a common purpose, and where they are fundamentally different. We discuss and relate the basic notions of both theories: Shannon entropy versus Kolmogorov complexity, the relation of both to universal coding, Shannon mutual information versus Kolmogorov ( algorithmic') mutual information, probabilistic sufficient statistic versus algorithmic sufficient statistic (related to lossy compression in the Shannon theory versus meaningful information in the Kolmogorov theory), and rate distortion theory versus Kolmogorov's structure function. Part of the material has appeared in print before, scattered through various publications, but this is the first comprehensive systematic comparison. The last mentioned relations are new. Since the very beginning the notion of complexity of finite objects was considered as an algorithmic counterpart to the notion of Shannon entropy. Kolmogorov's paper (1965) was called "Three approaches to the quantitative definition of information"; Shannon entropy and algorithmic complexity were among these approaches. It was mentioned by Kolmogorov later (1968) that the properties of algorithmic complexity and Shannon entropy are similar. We investigate one aspect of this similarity. Namely, we are interested in linear inequalities that are valid for Shannon entropies and for Kolmogorov complexities. It turns out that (1) all inequalities that are valid for Kolmogorov complexities, are also valid for Shannon entropies and vice versa; (2) all inequalities that are valid for Shannon entropies, are valid for ranks of finite subsets of linear spaces; (3) the opposite statement is not true: Ingleton's inequality (1971) is valid for ranks but not for Shannon entropies; (4) for some special cases all three classes of inequalities coincide and have simple description. We present an inequality for Kolmogorov complexities that implies Ingleton's inequality for ranks; another application of this inequality is a new simple proof of one of Gacs-Korner's results on common information. The paper investigates connections between linear inequalities that are valid for Shannon entropies and for Kolmogorov complexities.