Fixed Point Theorems on Partial Randomness

DOI10.1007/978-3-540-92687-0_29zbMATH Open1211.68222arXiv0903.3433OpenAlexW2167685571MaRDI QIDQ3605545FDOQ3605545

Authors: Kohtaro Tadaki 

Publication date: 24 February 2009

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

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).

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

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

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)

Cites Work

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

Cited In (9)

• Fixed point theorems on partial randomness
• Randomness on full shift spaces
• On the random version of Ważewski theorem
• JSL volume 79 issue 2 Cover and Front matter
• A Chaitin \(\Omega\) number based on compressible strings
• 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)