pith. sign in

arxiv: 2310.14807 · v8 · submitted 2023-10-23 · 🧮 math.LO · cs.IT· cs.LO· math.IT

On Chaitin's Heuristic Principle and Halting Probability

Saeed Salehi This is my paper

Pith reviewed 2026-05-24 07:07 UTC · model grok-4.3

classification 🧮 math.LO cs.ITcs.LOmath.IT
keywords Chaitin's Omegahalting probabilitydiscrete measuresheuristic principleinput-free programsalgorithmic randomnessKolmogorov complexity
0
0 comments X

The pith

Chaitin's Omega is not the halting probability of randomly chosen input-free programs under any infinite discrete measure.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper first tries to recover a limited form of Chaitin's heuristic principle that no theory proves a sentence heavier than itself under a suitable weighting. It then focuses on the second part, proving that the halting probability of input-free programs cannot equal Omega when the probability is defined by any infinite discrete measure on the program space. This result blocks the common reading of Omega as the chance that a random program halts. The authors also outline several alternative ways to define halting probabilities by choosing other measures.

Core claim

Chaitin's constant Omega is not equal to the total measure of halting input-free programs for any infinite discrete measure on the space of such programs. The argument shows that the standard definition of Omega cannot arise as a halting probability under this broad class of measures, and the paper supplies several explicit constructions that do produce well-defined halting probabilities instead.

What carries the argument

Infinite discrete measures on the set of input-free programs, which assign a halting probability equal to the sum of the measures of all halting programs.

If this is right

  • Omega loses its interpretation as a natural halting probability under any such measure.
  • Alternative measures must be used to obtain actual halting probabilities.
  • Chaitin's heuristic principle can be realized only inside restricted logical settings.
  • Different choices of measure produce different numerical values for the halting probability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result indicates that any probabilistic reading of Omega requires measures outside the infinite discrete class.
  • It raises the question of whether continuous or non-discrete assignments on program spaces could recover Omega as a halting probability.
  • Similar negative results may apply to other constants defined via program enumeration.

Load-bearing premise

The idea that randomly chosen input-free programs can be modeled by an infinite discrete measure on the program space.

What would settle it

Exhibit one infinite discrete measure on input-free programs for which the sum of the measures of the halting programs equals Omega.

read the original abstract

It would be a heavenly reward if there were a method of weighing theories and sentences in such a way that a theory could never prove a heavier sentence (Chaitin's Heuristic Principle). Alas, no satisfactory measure has been found so far, and this dream seemed too good ever to come true. In the first part of this paper, we attempt to revive Chaitin's lost paradise of heuristic principle as much as logic allows. In the second part, which is a joint work with M. Jalilvand and B. Nikzad, we study Chaitin's well-known constant Omega and show that this number is not a probability of halting the randomly chosen input-free programs under any infinite discrete measure. We suggest several methods for defining halting probabilities using various measures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper has two parts. The first attempts to revive Chaitin's heuristic principle as far as logic permits. The second part (joint with M. Jalilvand and B. Nikzad) studies Chaitin's constant Omega and claims to show that Omega is not the halting probability of randomly chosen input-free programs under any infinite discrete measure; it also suggests several methods for defining halting probabilities via various measures.

Significance. If the central claim of the second part is substantiated with a precise definition of the probability under infinite measures, the result would clarify the status of Omega and supply concrete alternatives for halting probabilities. The first part's revival of the heuristic principle could add value if it yields new formal constraints, but its significance is harder to gauge without the details of the constructions.

major comments (1)
  1. [Abstract (joint-work section)] Abstract (joint-work section): the claim that Omega cannot equal the halting probability under any infinite discrete measure requires an explicit definition of that probability. When the measure mu satisfies sum mu(p) = infinity the ratio sum_{halting} mu(p) / sum_all mu(p) is undefined; the manuscript must therefore supply the alternative normalization (limit, conditional measure, or other device) before the negative claim can be assessed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a point that requires clarification to make the central negative claim fully rigorous. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract (joint-work section)] Abstract (joint-work section): the claim that Omega cannot equal the halting probability under any infinite discrete measure requires an explicit definition of that probability. When the measure mu satisfies sum mu(p) = infinity the ratio sum_{halting} mu(p) / sum_all mu(p) is undefined; the manuscript must therefore supply the alternative normalization (limit, conditional measure, or other device) before the negative claim can be assessed.

    Authors: We agree that the abstract statement of the result is not self-contained and that an explicit normalization must be supplied before the claim can be evaluated. In the body of the paper we define the relevant halting probability for an infinite discrete measure μ via the limit lim_{N→∞} μ({p : |p|≤N and p halts}) / μ({p : |p|≤N}), which is the natural cylinder-based normalization that remains well-defined even when the total measure diverges. We will revise the abstract to state this normalization explicitly (or to refer the reader to the precise definition given in Section 3), thereby rendering the negative result assessable. This is a straightforward clarification rather than a change in substance. revision: yes

Circularity Check

0 steps flagged

No circularity; no load-bearing derivations or self-citations visible for inspection

full rationale

The supplied abstract states a negative result (Omega is not a halting probability under any infinite discrete measure) and mentions suggesting alternative definitions, but contains no equations, no formal definitions of the probability measure, and no citations. The skeptic note correctly flags that the comparison requires an explicit normalization when sums diverge, yet without any paper text exhibiting a derivation chain, no step can be quoted that reduces by construction to its inputs. Per rules, circularity requires an explicit quote showing reduction (e.g., fitted parameter renamed as prediction or self-citation load-bearing the central claim); none exists here. This is the normal honest non-finding when the text supplies no inspectable chain.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available, so the ledger cannot list specific free parameters, axioms, or invented entities with evidence from the paper.

pith-pipeline@v0.9.0 · 5653 in / 1010 out tokens · 17890 ms · 2026-05-24T07:07:54.708639+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 1 internal anchor

  1. [1]

    Aspects of Chaitin’s Omega

    B ARMPALIAS , G EORGE (2020); “Aspects of Chaitin’s Omega”, in: J.N.Y . Franklin & C.P. Porter (eds.), Algorithmic Randomness: Progress and Prospects , Lecture Notes in Logic 50, Cambridge University Press, pp. 175–205. DOI: 10.1017/9781108781718.007

    work page doi:10.1017/9781108781718.007 2020

  2. [2]

    (2006); Randomness and Halting Probabilities, The Journal of Symbolic Logic 71:4, pp

    B ECHER , V ER ´ONICA & F IGUEIRA , S ANTIAGO & G RIGORIEFF , S ERGE & M ILLER , J OSEPH S. (2006); Randomness and Halting Probabilities, The Journal of Symbolic Logic 71:4, pp. 1411–1430. DOI: 10.2178/jsl/1164060463

    work page doi:10.2178/jsl/1164060463 2006

  3. [4]

    & H ARRISON -TRAINOR , M ATTHEW (2021); Some Questions of Uniformity in Algorithmic Randomness, The Journal of Symbolic Logic 86:4, pp

    B IENVENU , L AURENT & C SIMA , B ARBARA F. & H ARRISON -TRAINOR , M ATTHEW (2021); Some Questions of Uniformity in Algorithmic Randomness, The Journal of Symbolic Logic 86:4, pp. 1612–

    work page 2021

  4. [5]

    DOI: 10.1017/jsl.2021.58

    work page doi:10.1017/jsl.2021.58 2021

  5. [6]

    1380–1402

    B IENVENU , L AURENT & R OMASHCHENKO , A NDREI & S HEN , A LEXANDER & T AVENEAUX , A N- TOINE & V ERMEEREN , S TIJN (2014); The Axiomatic Power of Kolmogorov Complexity, Annals of Pure and Applied Logic 165:9, pp. 1380–1402. DOI: 10.1016/j.apal.2014.04.009

    work page doi:10.1016/j.apal.2014.04.009 2014

  6. [7]

    & C HAITIN , GREGORY J

    C ALUDE , CRISTIAN S. & C HAITIN , GREGORY J. (2010); What Is ... a Halting Probability?, Notices of the American Mathematical Society 57:2, pp. 236–237. PAPER ID: rtx100200236p

    work page 2010

  7. [8]

    & J ¨URGENSEN , H ELMUT (2005); Is Complexity a Source of Incompleteness?, Advances in Applied Mathematics 35:1, pp

    C ALUDE , C RISTIAN S. & J ¨URGENSEN , H ELMUT (2005); Is Complexity a Source of Incompleteness?, Advances in Applied Mathematics 35:1, pp. 1–15. DOI: 10.1016/j.aam.2004.10.003

    work page doi:10.1016/j.aam.2004.10.003 2005

  8. [9]

    C HAITIN , G REGORY (1974); Information-Theoretic Limitations of Formal Systems, Journal of the As- sociation for Computing Machinery 21:3, pp. 403–424. DOI: 10.1145/321832.321839

    work page doi:10.1145/321832.321839 1974

  9. [10]

    (1975); A Theory of Program Size Formally Identical to Information Theory, Journal of the Association for Computing Machinery 22:3, pp

    C HAITIN , G REGORY J. (1975); A Theory of Program Size Formally Identical to Information Theory, Journal of the Association for Computing Machinery 22:3, pp. 329–340. DOI: 10.1145/321892.321894

    work page doi:10.1145/321892.321894 1975

  10. [11]

    (1988); Randomness in Arithmetic, Scientific American 259:1 (July), pp

    C HAITIN , GREGORY J. (1988); Randomness in Arithmetic, Scientific American 259:1 (July), pp. 80–85. JSTOR : 24989161

    work page 1988

  11. [12]

    C HAITIN , GREGORY (1992); LISP Program-Size Complexity II,Applied Mathematics and Computation 52:1, pp. 103–126. DOI: 10.1016/0096-3003(92)90100-F

    work page doi:10.1016/0096-3003(92)90100-f 1992

  12. [13]

    (1995); Randomness in Arithmetic and the Decline and Fall of Reductionism in Pure Mathematics, Chaos, Solitons & Fractals 5:2, pp

    C HAITIN , G REGORY J. (1995); Randomness in Arithmetic and the Decline and Fall of Reductionism in Pure Mathematics, Chaos, Solitons & Fractals 5:2, pp. 143–159. DOI: 10.1016/0960-0779(93)E0017-6

    work page doi:10.1016/0960-0779(93)e0017-6 1995

  13. [14]

    Meta Math! The Quest for Omega

    C HAITIN , G REGORY J. (2005); Meta Math!: The Quest for Omega , Pantheon Books. ISBN : 9780375423130 (The page numbers in the text refer to the pre-print arXiv:math/0404335v7)

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  14. [15]

    F ALLIS , DON (1996); The Source of Chaitin’s Incorrectness,Philosophia Mathematica 4:3, pp. 261–269. DOI: 10.1093/philmat/4.3.261

    work page doi:10.1093/philmat/4.3.261 1996

  15. [16]

    G ARDNER , MARTIN [& B ENNETT , CHARLES H.] (1979); Mathematical Games: The Random Number Omega Bids Fair to Hold the Mysteries of the Universe, Scientific American 241:5 (Nov.), pp. 20–35. JSTOR : 24965329

    work page 1979

  16. [17]

    (1916); The Mathematics of Common Things, School Science and Mathematics 16:8, pp

    G LAZIER , HARRIET E. (1916); The Mathematics of Common Things, School Science and Mathematics 16:8, pp. 667–674. DOI: 10.1111/j.1949-8594.1916.tb01753.x

    work page doi:10.1111/j.1949-8594.1916.tb01753.x 1916

  17. [18]

    G RENET , B RUNO (2010); Acceptable Complexity Measures of Theorems, Complex Systems 18:4, pp. 403–425. DOI: 10.25088/ComplexSystems.18.4.403

    work page doi:10.25088/complexsystems.18.4.403 2010

  18. [19]

    1007–1026

    H UNTER , ANTHONY & KONIECZNY , S ´EBASTIEN (2010); On the Measure of Conflicts: Shapley Incon- sistency Values,Artificial Intelligence 174:14, pp. 1007–1026. DOI: 10.1016/j.artint.2010.06.001

    work page doi:10.1016/j.artint.2010.06.001 2010

  19. [20]

    (1949); A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses, M.Sc

    K RAFT , LEON G. (1949); A Device for Quantizing, Grouping, and Coding Amplitude-Modulated Pulses, M.Sc. Thesis, MIT. URL: https://b2n.ir/m52630

    work page 1949

  20. [21]

    ISBN : 9783111324845

    L INDE , W ERNER (2024); Probability Theory: A First Course in Probability Theory and Statistics , De Gruyter (2nd ed.). ISBN : 9783111324845

    work page 2024

  21. [22]

    On Chaitin’s Heuristic Principle and Halting Probability, 2024

    work page 2024

  22. [23]

    (1978); basic BASIC: An Introduction to Programming, Edward Arnold (Publish- ers) Ltd

    M ONRO , DONALD M. (1978); basic BASIC: An Introduction to Programming, Edward Arnold (Publish- ers) Ltd. (1st ed.). ISBN : 0713127325 INTERNET ARCHIVE : basicbasicintrod0000monr

    work page 1978

  23. [24]

    (2021); Revisiting Chaitin’s Incompleteness Theorem,Notre Dame Journal of Formal Logic 62:1, pp

    P ORTER , C HRISTOPHER P. (2021); Revisiting Chaitin’s Incompleteness Theorem,Notre Dame Journal of Formal Logic 62:1, pp. 147–171. DOI: 10.1215/00294527-2021-0006

    work page doi:10.1215/00294527-2021-0006 2021

  24. [25]

    R AATIKAINEN , PANU (1998); On Interpreting Chaitin’s Incompleteness Theorem,Journal of Philosoph- ical Logic 27:6, pp. 569–586. DOI: 10.1023/A:1004305315546

    work page doi:10.1023/a:1004305315546 1998

  25. [26]

    The Secret Number: An Exposition of Chaitin’s Theory

    R OZENBERG , G RZEGORZ & S ALOMAA , A RTO (2007); “The Secret Number: An Exposition of Chaitin’s Theory”, in: C. S. Calude (ed.), Randomness and Complexity: From Leibniz to Chaitin (dedicated to Gregory J. Chaitin on the occasion of his 60th birthday), World Scientific, pp. 175–215. DOI: 10.1142/9789812770837 0011

    work page doi:10.1142/9789812770837 2007

  26. [27]

    S CHMIDHUBER , C HRISTOF (2022); Chaitin’s Omega and an Algorithmic Phase Transi- tion, Physica A: Statistical Mechanics and its Applications , 568 (Article 126458) pp. 1–15. DOI: 10.1016/j.physa.2021.126458

    work page doi:10.1016/j.physa.2021.126458 2022

  27. [28]

    URL: https://gupea.ub.gu.se/handle/2077/19472

    S J ¨OGREN , J ¨ORGEN (2004); Measuring the Power of Arithmetical Theories, Licentiate Thesis, University of Gothenburg, Department of Philosophy. URL: https://gupea.ub.gu.se/handle/2077/19472

    work page 2004

  28. [29]

    the Power of an Arithmetical Theory

    S J ¨OGREN , J ¨ORGEN (2008); On Explicating the Concept “the Power of an Arithmetical Theory”,Journal of Philosophical Logic 37:2, pp. 183–202. DOI: 10.1007/s10992-007-9077-8

    work page doi:10.1007/s10992-007-9077-8 2008

  29. [30]

    1389–1400

    VAN LAMBALGEN , M ICHIEL (1989); Algorithmic Information Theory, The Journal of Symbolic Logic 54:4, pp. 1389–1400. DOI: 10.2307/2274821

    work page doi:10.2307/2274821 1989