Fixed Point Theorems on Partial Randomness

DOI10.1007/978-3-540-92687-0_29MaRDI QIDQ3605545zbMATH OpenOpenAlexFDO

Authors Kohtaro Tadaki

Publication date 24 February 2009

Published in Logical Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.3433

zbMATH Keywords

fixed-point theoremalgorithmic randomnesspartial randomnessalgorithmic information theorythermodynamic quantitiesChaitin's \(\Omega \) number

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Foundations of equilibrium statistical mechanics (82B03)

Abstract: In our former work [K. Tadaki, Local Proceedings of CiE 2008, pp.425-434, 2008], we developed a statistical mechanical interpretation of algorithmic information theory by introducing the notion of thermodynamic quantities at temperature T, such as free energy F(T), energy E(T), and statistical mechanical entropy S(T), into the theory. These quantities are real functions of real argument T>0. We then discovered that, in the interpretation, the temperature T equals to the partial randomness of the values of all these thermodynamic quantities, where the notion of partial randomness is a stronger representation of the compression rate by program-size complexity. Furthermore, we showed that this situation holds for the temperature itself as a thermodynamic quantity. Namely, the computability of the value of partition function Z(T) gives a sufficient condition for T in (0,1) to be a fixed point on partial randomness. In this paper, we show that the computability of each of all the thermodynamic quantities above gives the sufficient condition also. Moreover, we show that the computability of F(T) gives completely different fixed points from the computability of Z(T).

Recommendations

• Fixed point theorems on partial randomness
• Algorithmic information theory and its statistical mechanical interpretation
• A statistical mechanical interpretation of algorithmic information theory. III: Composite systems and fixed points
• Algorithmic thermodynamics
• Computability at zero temperature

Cites work

• scientific article; zbMATH DE number 1332581 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1762479 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Algorithmic Information Theory
• Algorithmic randomness and complexity.
• Effectively closed sets of measures and randomness
• Hierarchies of randomness tests
• Infinite subsets of random sets of integers
• Natural halting probabilities, partial randomness, and zeta functions
• On partial randomness
• Statistical physics I. Equilibrium statistical mechanics. Rev. transl. from the Japanese ed. by Morikazu Toda and Nobuhiko Saitô.

Cited in

(9)

• Fixed point theorems on partial randomness
• Randomness on full shift spaces
• On the random version of Ważewski theorem
• A Chaitin number based on compressible strings
• JSL volume 79 issue 2 Cover and Front matter
• A statistical mechanical interpretation of algorithmic information theory. III: Composite systems and fixed points
• Introduction to the special issue: Computability of the physical
• Partial Randomness and Dimension of Recursively Enumerable Reals
• Theorems on the variable-length intrinsic randomness

This page was built for publication: Fixed Point Theorems on Partial Randomness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3605545)