Phase transition between unidirectionality and bidirectionality

DOI10.1007/978-3-642-27654-5_16MaRDI QIDQ2891313zbMATH OpenOpenAlexFDO

Authors Kohtaro Tadaki

Publication date 15 June 2012

Published in Computation, Physics and Beyond (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Statistical thermodynamics (82B30) Other degrees and reducibilities in computability and recursion theory (03D30) Foundations of equilibrium statistical mechanics (82B03)

Abstract: The notion of weak truth-table reducibility plays an important role in recursion theory. In this paper, we introduce an elaboration of this notion, where a computable bound on the use function is explicitly specified. This elaboration enables us to deal with the notion of asymptotic behavior in a manner like in computational complexity theory, while staying in computability theory. We apply the elaboration to sets which appear in the statistical mechanical interpretation of algorithmic information theory. We demonstrate the power of the elaboration by revealing a critical phenomenon, i.e., a phase transition, in the statistical mechanical interpretation, which cannot be captured by the original notion of weak truth-table reducibility.

Recommendations

• Phase transition and strong predictability
• Bounds in weak truth-table reducibility
• A New Reducibility between Turing‐ and wtt‐Reducibility
• Computational depth and reducibility
• Computational depth and reducibility

Cites work

• scientific article; zbMATH DE number 1543065 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (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.
• Chaitin numbers and halting problems
• Computability and Randomness
• Hierarchies of randomness tests
• Natural halting probabilities, partial randomness, and zeta functions
• On initial segment complexity and degrees of randomness
• On partial randomness
• Partial Randomness and Dimension of Recursively Enumerable Reals
• Randomness and recursive enumerability
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Representation of left-computable \(\varepsilon \)-random reals

Cited in

(2)

• Algorithmic information theory and its statistical mechanical interpretation
• Chaitin's omega and an algorithmic phase transition

This page was built for publication: Phase transition between unidirectionality and bidirectionality

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