Probabilistic — measure, chance, and limits

Parent: relaxing-undecidability

Trade a definite yes/no for a measure or a probability-1 statement.

Chaitin's Ω — the measure of halting

Halting probability

For a prefix-free universal machine U, $\Omega = \sum_p 2^{-|p|}$ over programs p that halt — the probability a random program halts.

Ω is algorithmically random (its bits are incompressible) and uncomputable, yet left-c.e.: computable from below (run more programs, Ω only rises). So halting has an approximable numeric "amount," even though no bit is decidable. Its bits are irreducible mathematical facts.

Almost-sure convergence

In stochastic dynamics you replace "converges" with "converges with probability 1" (stochastic approximation, Robbins–Monro; martingale convergence). The exceptional non-converging paths form a measure-zero set — invisible to the dynamics.

Computable in the limit (Gold, 1965)

Limiting recursion / trial-and-error: output a guess, and be allowed to change it finitely often; the final guess is correct. The (total) halting predicate is computable this way — it's Δ₂. You never know you're done, but you're right in the limit.

Tie: self-evolving agents that "usually converge" live here — almost-sure / limit convergence, not decidable convergence; the residual uncertainty is exactly why a certificate or tolerance is still needed to commit.