A Generalization of Chaitin's Halting Probability Ωand Halting Self-Similar Sets

Abstract

We generalize the concept of randomness in an infinite binary sequence in order to characterize the degree of randomness by a real number D>0. Chaitin's halting probability Ωis generalized to Ω^D whose degree of randomness is precisely D. On the basis of this generalization, we consider the degree of randomness of each point in Euclidean space through its base-two expansion. It is then shown that the maximum value of such a degree of randomness provides the Hausdorff dimension of a self-similar set that is computable in a certain sense. The class of such self-similar sets includes familiar fractal sets such as the Cantor set, von Koch curve, and Sierpinski gasket. Knowledge of the property of Ω^D allows us to show that the self-similar subset of [0,1] defined by the halting set of a universal algorithm has a Hausdorff dimension of one.

29 pages, LaTeX2e, AMSLaTeX1.2, \usepackage{a4wide}, no figures

Cited by in corpus (15)

• Thermodynamic costs of Turing Machines
• Translating the Cantor set by a random
• A statistical mechanical interpretation of instantaneous codes
• The Tsallis entropy and the Shannon entropy of a universal probability
• An extension of Chaitin's halting probability Ωto a measurement operator in an infinite dimensional quantum system
• Phase Transition and Strong Predictability
• Partial randomness and dimension of recursively enumerable reals
• A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points
• Fixed point theorems on partial randomness
• A Computational Complexity-Theoretic Elaboration of Weak Truth-Table Reducibility
• A superstatistical formulation of complexity measures
• Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences
• Algorithmic Thermodynamics
• A generalization of Levin-Schnorr's theorem
• A new representation of Chaitin Ωnumber based on compressible strings