A Variant Of Chaitin's Omega function

The Big Picture: The "Halting Probability" Machine

Imagine you have a magical, infinite library of books. Each book contains a computer program. Some of these programs are well-written and will eventually stop running (they "halt"). Others are broken loops that will run forever.

In the 1970s, a mathematician named Gregory Chaitin invented a number called Omega ( $\Omega$ ). You can think of Omega as the total probability that if you picked a random book from this infinite library, it would be a program that stops.

It's a number between 0 and 1.
It's incredibly complex. In fact, it's so random that you cannot predict any of its digits. It's the "champion of randomness."
However, Omega is usually defined as a single, static number.

The New Idea: Turning the Dial

The authors of this paper (Li, Zhang, Zhang, and Zhao) asked a fun question: What if we didn't just pick one random book, but instead turned a dial to select a specific section of the library?

They defined a new function, let's call it $f(x)$ .

Imagine the library is arranged in a giant line, sorted alphabetically.
You have a slider (represented by $x$ ) that moves along this line.
As you slide your finger to position $x$ , the function $f(x)$ adds up the "weights" (probabilities) of all the stopping programs that appear to the left of your finger.

So, $f(x)$ is a continuous function. As you move your slider smoothly from left to right, the value of $f(x)$ grows smoothly. It's like filling a bucket with water from a tap that flows at a rate determined by the complexity of the programs you pass.

What Did They Discover?

The paper investigates what happens when you use this "slider function." Here are their main findings, explained with analogies:

1. The Smoothness Test (Differentiability)

In math, a function is "differentiable" if it has a smooth slope at a specific point (like a gentle hill) rather than a jagged edge (like a cliff).

The Finding: The function $f(x)$ is smooth only at points that are "Density Random."
The Analogy: Imagine walking on a path made of sand. Most of the path is jagged and rocky. But if you stand on a spot that is "perfectly random" (in a very specific statistical sense), the ground feels perfectly flat under your feet. If you aren't perfectly random, the ground is jagged, and you can't define a smooth slope.

2. The Shape of the Bucket (The Range)

If you slide your finger from the very beginning to the very end of the library, what is the shape of the water level in the bucket?

The Finding: The set of all possible values $f(x)$ can take is a Cantor Set.
The Analogy: Think of the Cantor set as a piece of Swiss cheese or a sponge. It is a solid-looking shape, but if you zoom in, you see it's full of holes. It has no "solid" chunks (nowhere dense), but it is also infinitely detailed (perfect).
Surprise: Even though this shape looks like it has "holes" everywhere, it is actually "thick" in a mathematical sense called Hausdorff dimension 1. It's like a fractal that is so crinkly it fills up the space as much as a solid line, even though it has no area.

3. The Randomness Connection

Does the output $f(x)$ stay as random as the input $x$ ?

The Finding: It depends on the "complexity" of $x$ $x$ .
- If $x$ is a "simple" random number (mathematically called "weakly low for K"), then $f(x)$ is just as random as $x$ .
- If $x$ is "too complex" or "too structured," $f(x)$ might lose its randomness.
The Analogy: Imagine $x$ is a secret code. If the code is "weak" (simple), the machine $f$ scrambles it perfectly, and the output is a new, unbreakable code. But if the code is "strong" (too complex), the machine gets confused, and the output might reveal patterns, making it less random.

4. The "Unpredictable" Exceptions

The authors proved that for almost all numbers $x$ , the output $f(x)$ is a perfectly random number. However, they also proved that there are infinitely many specific numbers $x$ where the output $f(x)$ is not random at all.

The Analogy: Imagine a lottery machine that works perfectly 99.9% of the time. But the authors found a way to rig the machine for specific, rare tickets so that the machine produces a predictable, boring number (like 0.500000) instead of a random one. They showed you can create a whole "forest" of these rigged tickets.

5. The "Turing" Trap

In computer science, "Turing invariant" means that if two numbers are computationally equivalent (you can turn one into the other with a computer program), their outputs should also be equivalent.

The Finding: This function $f$ is not generally Turing invariant.
The Analogy: Imagine two people, Alice and Bob, who are equally smart (computationally equivalent). If they both use this machine, Alice might get a random, chaotic result, while Bob gets a predictable, boring result. The machine treats them differently, even though they are "equal" in power. However, if they are both "K-trivial" (a very specific type of simple number), the machine treats them fairly.

Why Does This Matter?

This paper is like taking a famous, mysterious machine (Chaitin's Omega) and putting it on a treadmill.

It helps mathematicians understand the boundary between order and chaos.
It shows that even in the world of pure randomness, there are "sweet spots" (density random points) where things become smooth and predictable.
It connects the abstract idea of "randomness" to the physical shape of numbers (geometry and dimension).

In short, the authors built a new mathematical lens to look at randomness, showing us that while randomness is usually wild and untamable, it has hidden structures, smooth spots, and surprising exceptions that we can now map out.

1. Problem Statement and Motivation

The paper investigates a continuous variant of Chaitin's Omega function, denoted as $f$ . While Chaitin's original $\Omega$ is a specific real number representing the halting probability of a universal prefix-free machine, and previous works (e.g., Hölzl et al.) have defined continuous functions based on initial segments of reals ( $\hat{\Omega}(x) = \sum_{\sigma \prec x} 2^{-K(\sigma)}$ ), this paper focuses on a different summation domain.

The authors define the function $f: 2^\omega \to [0, 1]$ as:
$f(x) = \sum_{\sigma \le_L x} 2^{-K(\sigma)}$
where $\sigma \le_L x$ means $\sigma$ is either an initial segment of $x$ or $\sigma$ is lexicographically to the left of $x$ (i.e., $\sigma \prec_L x$ ).

The primary goal is to analyze $f$ from the perspectives of mathematical analysis (differentiability, range structure), computability theory (Turing degrees, lowness properties), and algorithmic randomness (randomness of the output $f(x)$ relative to the input $x$ ). The authors aim to contrast $f$ with the previously studied $\hat{\Omega}$ function and other Omega variants.

2. Methodology

The authors employ a multidisciplinary approach combining:

Algorithmic Information Theory: Utilizing prefix-free Kolmogorov complexity $K(\sigma)$ , Solovay reducibility, and properties of left-c.e. reals.
Measure Theory and Analysis: Investigating the function as an "interval-c.e." function, analyzing its differentiability using Lebesgue density theorems, and calculating the Hausdorff dimension of its range.
Computability Theory: Using oracle machines, Turing reducibility ( $\le_T$ ), and lowness notions (e.g., $K$ -triviality, weak lowness for $K$ ).
Construction Techniques: Employing the Machine Existence Theorem (via Kraft-Chaitin sets) to construct optimal machines with specific properties and using perturbation lemmas to control the values of $f(x)$ .

3. Key Contributions and Results

A. Analytic Properties

Differentiability: The function $f$ $f$ (viewed as a real function $F$ $F$ via binary expansion) is differentiable precisely at density random points.
- If $x$ is not density random, $F$ is not differentiable at $x$ .
- If $F$ is differentiable at $x$ , the derivative $F'(x) = 0$ .
- This contrasts with $\hat{\Omega}$ , which is differentiable exactly at 1-random reals. Since density randomness is a strictly stronger condition than 1-randomness, $f$ is "less differentiable" than $\hat{\Omega}$ .
Monotonicity: Unlike $\hat{\Omega}$ , which is nowhere monotone, $f$ is strictly monotone increasing with respect to the lexicographical order ( $x <_L y \implies f(x) < f(y)$ ).
Structure of the Range $f(2^\omega)$ :
- The range is a null set (Lebesgue measure 0).
- It is nowhere dense (its closure has empty interior).
- It is a perfect set (closed with no isolated points).
- The range is constructed similarly to a Cantor ternary set but with variable gap sizes.
- Hausdorff Dimension: Despite being a null set, the Hausdorff dimension of the range is 1. This is proven by mapping the range to generalized Cantor sets $C_\gamma$ for any scale $\gamma > 1$ via Lipschitz functions.

B. Complexity and Turing Degrees

Computability of Values: For any real $x$ , $f(x)$ is left- $x$ -c.e. (computably enumerable relative to $x$ ).
Turing Equivalence: The join of the input and output computes the halting problem:
$f(x) \oplus x \ge_T \emptyset'$
Consequently, any two of $\{x, f(x), \emptyset'\}$ can compute the third.
Non-Computability: If $f(x)$ is computable, then $x$ must be right-c.e. and Turing complete (though the existence of such an $x$ remains an open question).
Randomness of Output:
- $f(x)$ is not generally $x$ -random.
- However, $f(x)$ is not $\emptyset'$ -Kurtz random for any $x$ (since the range is a $\Pi^0_1(\emptyset')$ class).

C. Randomness Characterizations

The paper establishes a precise characterization linking the lowness of the input to the randomness of the output:

Main Theorem: $f(x)$ $f (x)$ is $x$ -random if and only if $x$ is weakly low for $K$ .
- Note: Being "weakly low for $K$ " is equivalent to being "low for $\Omega$ " (Miller's Theorem).
Corollaries:
- If $x$ is 2-random, $f(x)$ is $x$ -random (and thus 1-random).
- If $x$ is $K$ -trivial, $f(x)$ is an Omega number (a left-c.e. 1-random real) and is Turing equivalent to $\emptyset'$ .
- Turing Invariance: $f$ is not Turing invariant in general (i.e., $x \equiv_T y$ does not imply $f(x) \equiv_T f(y)$ ). However, $f$ is Turing invariant (specifically weak truth-table invariant) when restricted to the ideal of $K$ -trivial reals.

D. Negative Results (Non-Random Outputs)

Despite the fact that "most" inputs yield random outputs, the authors prove the existence of non-random outputs:

Existence of Non-1-Random Outputs: There exists a real $x \le_T \emptyset'$ $x \leq_{T} \emptyset^{'}$ such that $f(x)$ $f (x)$ is not 1-random.
- The proof utilizes a "Small Perturbation Lemma" to construct $x$ such that $f(x)$ fails to be normal (and thus fails 1-randomness).
Cardinality: There are $2^{\aleph_0}$ many such reals $x$ for which $f(x)$ is not 1-random. This is shown by constructing a perfect tree of such reals.

E. Relation to Other Omega Variants

The authors relate $f$ to the Omega operator $\Omega[X] = \sum_{V(\sigma) \in X} 2^{-|\sigma|}$ defined by Becher et al.

$f(x)$ can be viewed as the restriction of $\Omega[X]$ to the set $X = \{\sigma : \sigma \le_L x\}$ .
They generalize a result by Becher et al.: If $a$ is a left-c.e. 1-random real and $x$ is a left-c.e. real, there exists an optimal machine $V$ such that $f_V(x) = a$ .

4. Significance

This paper makes several significant contributions to the theory of algorithmic randomness and computable analysis:

New Differentiability Threshold: It identifies density randomness as the exact threshold for the differentiability of this specific Omega variant, distinguishing it from the 1-randomness threshold of the initial-segment variant ( $\hat{\Omega}$ ).
Geometric Structure: It reveals that the range of $f$ is a "fat" null set (Hausdorff dimension 1) with a Cantor-like structure, providing a new example of a set with these specific topological and measure-theoretic properties in the context of algorithmic randomness.
Lowness-Randomness Duality: It provides a clean equivalence ( $x$ is weakly low for $K \iff f(x)$ is $x$ -random), offering a new characterization of weak lowness for $K$ .
Counterexamples: It demonstrates that even for "nice" continuous functions derived from Omega, the output is not guaranteed to be random for all inputs, and specifically constructs a large set of inputs yielding non-random outputs, challenging the intuition that Omega-like functions always produce random numbers.
Turing Invariance: It clarifies the limits of Turing invariance for Omega-like functions, showing invariance holds only within specific ideals (like $K$ -trivials) but fails globally.

5. Open Questions

The authors conclude by raising several open questions, including:

Does the range $f(2^\omega)$ contain any computable real?
Is $f$ Turing invariant on degrees of non- $K$ -trivial reals?
Is there an $x$ such that $f(x)$ has hyperimmune-free degree?

In summary, the paper successfully establishes $f$ as a rich mathematical object that bridges analysis, computability, and randomness, offering new insights into the structural properties of Chaitin's Omega and its variants.