Natural halting probabilities, partial randomness, and zeta functions

DOI10.1016/j.ic.2006.07.003zbMath1171.68505OpenAlexW2143588186WikidataQ57001640 ScholiaQ57001640MaRDI QIDQ859830

Cristian S. Calude, Michael A. Stay

Publication date: 22 January 2007

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/631/

zbMATH Keywords

zeta functionTuring machinehalting probabilityrandom realomega numberTuatara machinezeta number

Mathematics Subject Classification ID

(zeta (s)) and (L(s, chi)) (11M06) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (15)

Phase Transition between Unidirectionality and Bidirectionality ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ Introduction: computability of the physical ⋮ Renormalisation and computation II: time cut-off and the Halting Problem ⋮ A statistical mechanical interpretation of algorithmic information theory III: composite systems and fixed points ⋮ Algorithmic thermodynamics ⋮ Chaitin's omega and an algorithmic phase transition ⋮ Anytime Algorithms for Non-Ending Computations ⋮ Fixed point theorems on partial randomness ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Most programs stop quickly or never halt ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Fixed Point Theorems on Partial Randomness ⋮ On universal computably enumerable prefix codes ⋮ Information: The Algorithmic Paradigm

Cites Work

• LISP program-size complexity. II
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• The Kolmogorov complexity of real numbers.
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• On partial randomness
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• A Theory of Program Size Formally Identical to Information Theory
• Very Simple Chaitin Machines for Concrete AIT
• On the Length of Programs for Computing Finite Binary Sequences
• Recursion Theory and Dedekind Cuts
• On the entropy of context-free languages
• Complexity oscillations in infinite binary sequences
• From Heisenberg to Gödel via Chaitin
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Natural halting probabilities, partial randomness, and zeta functions