On Chaitin's Heuristic Principle and Halting Probability

This paper attempts to revive Chaitin's Heuristic Principle for weighing theories while demonstrating that Chaitin's constant Omega is not a halting probability under any infinite discrete measure, subsequently proposing alternative methods for defining halting probabilities.

The Gist

The Big Picture: Two Lost Dreams

Imagine you are an architect trying to build a tower of knowledge. You have a set of blueprints (axioms) and you want to build rooms (theorems) on top of them.

This paper tackles two famous "dreams" in mathematics that turned out to be slightly flawed:

1. The Weight Dream: Can we put a "weight" on our blueprints and our rooms so that a room can never be heavier than the blueprints that built it? (If your blueprints are light, you can't build a heavy room).
2. The Coin Toss Dream: If you flip a coin to generate a computer program bit-by-bit, is the number $\Omega$ (Omega) the exact probability that the resulting program will stop running?

The author, Saeed Salehi, says: "The first dream was a beautiful illusion, and the second dream was a misunderstanding of the rules of probability." Let's break it down.

---

Part 1: The "Weight" of Knowledge (Chaitin's Heuristic Principle)

The Original Idea

Gregory Chaitin, a genius mathematician, once proposed a simple rule: "You cannot prove a heavy theorem using light axioms."

• The Analogy: Imagine your axioms are a backpack. If your backpack weighs 10 pounds, you cannot carry a 20-pound rock out of it. The rock (theorem) must weigh less than or equal to the backpack (theory).
• The Goal: We want a scale that measures the "complexity" (weight) of a theory and a sentence. If the sentence is heavier, the theory can't prove it.

Why the Original Idea Failed

Salehi explains that previous attempts to weigh things failed because of "tricky logic."

• The Problem: In math, you can have a "trick" sentence. Imagine a sentence that says, "If 2+2=5, then I am the King of France." This is a logical tautology (it's always true), so it should be easy to prove. But if you measure its "complexity" by how long the sentence is or how hard it is to write a program to output it, it might look "heavy."
• The Result: You could have a "light" theory proving a "heavy" sentence. The scale broke.
• The Fix: Salehi suggests we need a new kind of scale. Instead of measuring "complexity" (like the length of a program), we should measure logical power.
  • The New Scale: Imagine a scale that simply asks: "Does this theory prove this sentence?"
  • If Theory A proves Sentence B, then A is "heavier" (or equal) to B.
  • If Theory A cannot prove Sentence B, then B is "heavier" than A.
  • This works perfectly, but it's not a simple number like "5 pounds." It's a complex, multi-dimensional map of what can be proven.

The Takeaway: You can't weigh theories with a simple ruler (like Kolmogorov complexity). You need a map of logical relationships. If you try to force a simple number onto it, the math breaks.

---

Part 2: The "Halting Probability" (The Omega Number)

The Original Idea

Chaitin also defined a famous number called $\Omega$ (Omega).

• The Story: Imagine you have a coin. You flip it to generate a computer program. Heads = 0, Tails = 1. You keep flipping until the program stops (halts).
• The Claim: $\Omega$ is the probability that a randomly generated program will eventually stop running. It was thought to be the "ultimate random number," holding the secrets of the universe.

Why the Original Idea Was Wrong

Salehi argues that $\Omega$ is not the probability of a random string being a halting program. Here is the analogy:

The "Bag of Strings" Analogy:
Imagine you have a giant bag containing every possible string of 0s and 1s (like "0", "1", "00", "01", "10", "11", etc.).

1. The Mistake: Chaitin's formula ($\Omega = \sum 2^{-|p|}$) adds up the probabilities of specific strings.
2. The Reality: If you pull a random string out of the bag, it is almost certainly not a valid computer program. It's just gibberish.
   • It might be a program that needs input (like "Type in a number first").
   • It might be a program that runs forever (infinite loop).
   • It might be a program that doesn't exist in your specific language.

The "Sample Space" Problem:
In probability, the total probability of everything that can happen must equal 1.

• Salehi shows that if you sum up the probabilities of all "halting programs" using Chaitin's formula, the total is less than 1.
• Why? Because the "bag" contains a lot of junk (non-programs) and programs that don't halt. The "halting programs" are just a tiny, incomplete slice of the pie.
• Therefore, $\Omega$ is not a probability of a random string halting. It's just a number that happens to be between 0 and 1.

The Correct Interpretation: The "Real Number" Analogy

So, what is $\Omega$? Salehi offers a beautiful correction.

Imagine you are not picking a string from a bag. Instead, imagine you are picking a real number (a point on a line between 0 and 1).

• Every real number has an infinite binary expansion (like 0.101101...).
• $\Omega$ is the probability that if you pick a random real number, its beginning (prefix) matches the code of a halting program.

The Analogy:
Think of a library where every book is a real number.

• $\Omega$ isn't the chance that you pick a book that is a halting program.
• $\Omega$ is the chance that the first few pages of the book you pick match the start of a halting program.

Salehi suggests that if we want a true "Halting Probability" for strings, we need to normalize it. We should divide the weight of halting programs by the total weight of all valid programs. This creates a new number (let's call it $\Upsilon$) that actually behaves like a probability.

---

Summary of the Paper's "Aha!" Moments

1. The Weight Principle: You can't measure the "weight" of a math theory with a simple ruler (complexity). You have to look at the logical structure. If you try to force a simple number, you get contradictions.
2. The Omega Number: $\Omega$ is not the chance that a random string is a halting program. It is the chance that a random real number starts with a halting program.
3. The Probability Fix: To make $\Omega$ a true probability for strings, we have to change the rules of the game (the "measure"). We can't just use the standard coin-flip method; we have to account for the fact that most random strings aren't programs at all.

The Final Verdict

The paper is a "reality check" for two of the most famous ideas in computer science. It tells us that while Chaitin's ideas were brilliant and revolutionary, they were slightly misinterpreted.

• Heuristic Principle: It's a dream that needs a better map, not a better scale.
• Halting Probability: It's not a coin flip for strings; it's a geometric property of real numbers.

As the author concludes, mathematics is the science of learning how not to compute. Sometimes, the most important thing is realizing that the number you thought was the answer is actually asking a different question.

Technical Summary

1. Problem Statement

The paper addresses two fundamental issues in Algorithmic Information Theory (AIT) and mathematical logic:

1. Chaitin's Heuristic Principle (HP): The intuitive notion that a formal theory cannot prove a theorem that contains more "information" (complexity) than the theory itself. The author investigates whether a rigorous, real-valued "weighting" function exists that satisfies this principle, noting that previous attempts using Kolmogorov complexity ($K$) or $\delta$-complexity ($K(x) - |x|$) have been proven false or insufficient.
2. The Nature of Chaitin's Constant ($\Omega$): The paper challenges the standard interpretation of $\Omega$ as the "probability that a randomly chosen input-free program halts." It argues that $\Omega$ does not satisfy the axioms of a probability measure over the space of finite binary strings (programs) under any standard discrete measure, despite being widely cited as such.

2. Methodology

The paper is divided into two distinct parts employing different mathematical tools:

• Part I (Logic and Weighing Theories):

  • Formal Logic: Uses propositional and first-order logic to define theories, axioms, and provability relations ($T \vdash \psi$).
  • Order Theory: Analyzes the hierarchy of theories (e.g., extensions of Robinson's Arithmetic $Q$) to demonstrate the existence of infinite chains and incomparable theories.
  • Constructive Definitions: Defines various mapping functions (weightings) $W$ from theories to real numbers and tests them against the Heuristic Principle (HP) and the newly proposed Equivalence Principle (EP).
  • Computability Theory: Investigates the computability of these weightings in relation to the decidability of the underlying logic.

• Part II (Measure Theory and Probability):

  • Measure Theory: Applies Kolmogorov's axioms of probability and Lebesgue measure on the unit interval $(0, 1]$.
  • Prefix-Free Codes: Utilizes Kraft's Inequality and the concept of prefix-free sets (self-delimiting programs) to analyze the convergence of series defining $\Omega$.
  • Counter-Examples and Proofs: Constructs specific probability distributions and sample spaces to disprove the claim that $\Omega$ represents the halting probability of finite strings.

3. Key Contributions and Results

Part I: Weighing Theories and the Heuristic Principle

• Refutation of Existing Measures: The author proves that neither Kolmogorov complexity ($K$) nor $\delta$-complexity satisfies the Heuristic Principle. Specifically, it is shown that for any sound theory $T$, there are provable theorems with complexity greater than $T$ (e.g., tautologies like $\bot \to S$).
• The Necessity of Min/Max: The paper proves that any weighting satisfying HP must have a minimum and maximum value. Consequently, integer-valued weightings (like $K$) cannot satisfy HP for arithmetical theories because these theories form an infinite, pseudo-dense hierarchy (Theorem I.2.3).
• The Equivalence Principle (EP): To make HP non-trivial, the author introduces the Equivalence Principle (EP): $W(T) = W(U) \implies T \equiv U$ (theories are logically equivalent).
• Construction of Valid Weightings:
  • The author constructs a real-valued mapping $V(T) = \sum_{n>0} 2^{-n} W_{\{\psi_n\}}(T)$, where $W_{\{\psi_n\}}$ is a binary indicator of provability.
  • Theorem I.3.8: This mapping $V$ satisfies both HP and EP.
  • Computability Constraint: Theorem I.3.9 establishes that if the underlying logic is undecidable (e.g., first-order logic), no weighting satisfying both HP and EP can be computable. However, computable weightings satisfying HP (but not EP) exist for decidable logics.

Part II: Re-evaluating Halting Probability ($\Omega$)

• $\Omega$ is Not a Discrete Probability: The paper rigorously demonstrates that $\Omega = \sum_{p \in H} 2^{-|p|}$ is not the probability of a randomly chosen finite binary string being a halting program under any discrete probability measure on the set of all finite strings $\Sigma$.
  • Theorem II.4.3: For any probability measure $\pi$ on $\Sigma$, the actual probability of halting is strictly less than $\Omega$. The series defining $\Omega$ assumes a specific distribution (geometric with $p=1/2$) that does not sum to 1 over the space of all possible strings unless restricted to a specific prefix-free set with $\Omega=1$, which the set of all programs is not.
• The Correct Interpretation (Real Numbers): The paper clarifies that $\Omega$ is actually the Lebesgue measure of a set of real numbers.
  • Corollary II.4.6: $\Omega$ is the probability that a randomly chosen real number $\alpha \in (0, 1]$ has an infinite binary expansion that begins with a prefix corresponding to a halting program.
• Proposed Remedies:
  • Normalized Measure ($\mathfrak{U}$): The authors suggest defining a true probability measure on the set of input-free programs $P$ by normalizing: $\mathfrak{U}_S = \Omega_S / \Omega_P$.
  • Alternative Distributions: The paper suggests that halting probabilities can be defined using other distributions (e.g., Poisson, or geometric with $p \neq 1/2$) by mapping strings to integers, yielding different values that still retain the non-computable properties of $\Omega$.

4. Significance

• Logical Rigor: The paper rescues Chaitin's Heuristic Principle from being dismissed as a "dream" by providing mathematically sound, albeit non-computable (in undecidable logics), weightings that satisfy the principle. It clarifies the limitations of using complexity measures as direct proxies for information content in proofs.
• Correction of Misconceptions: It corrects a widespread pedagogical and popular misconception regarding Chaitin's $\Omega$. It clarifies that while $\Omega$ is a "random real," it is not the probability of a discrete event (picking a program) but rather a continuous measure (picking a real number).
• Foundational Impact: By distinguishing between discrete string probabilities and continuous real-number measures, the paper refines the understanding of Algorithmic Information Theory. It highlights that the "halting probability" is dependent on the choice of the sample space and the measure, and that $\Omega$ specifically relies on the Lebesgue measure of the unit interval.
• Computability Limits: The results reinforce the deep connection between the decidability of a logic and the computability of information-theoretic measures, showing that satisfying strong logical principles (HP + EP) in undecidable systems necessitates uncomputability.

In summary, Salehi provides a rigorous reconstruction of the Heuristic Principle through novel weightings and a critical re-analysis of Chaitin's constant, shifting its interpretation from a discrete halting probability to a continuous measure on real numbers.