Logical Inductors

Abstract

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running computations, and its own probabilities. We show that our algorithm, an instance of what we call a logical inductor, satisfies a number of intuitive desiderata, including: (1) it learns to predict patterns of truth and falsehood in logical statements, often long before having the resources to evaluate the statements, so long as the patterns can be written down in polynomial time; (2) it learns to use appropriate statistical summaries to predict sequences of statements whose truth values appear pseudorandom; and (3) it learns to have accurate beliefs about its own current beliefs, in a manner that avoids the standard paradoxes of self-reference. For example, if a given computer program only ever produces outputs in a certain range, a logical inductor learns this fact in a timely manner; and if late digits in the decimal expansion of $π$ are difficult to predict, then a logical inductor learns to assign $\approx 10\%$ probability to "the $n$th digit of $π$ is a 7" for large $n$. Logical inductors also learn to trust their future beliefs more than their current beliefs, and their beliefs are coherent in the limit (whenever $φ\implies ψ$, $\mathbb{P}_\infty(φ) \le \mathbb{P}_\infty(ψ)$, and so on); and logical inductors strictly dominate the universal semimeasure in the limit. These properties and many others all follow from a single logical induction criterion, which is motivated by a series of stock trading analogies. Roughly speaking, each logical sentence $φ$ is associated with a stock that is worth \$1 per share if [...]

Summary

This paper introduces logical inductors, a computable algorithm that assigns and refines probabilities to logical statements in formal languages over time, satisfying numerous desirable epistemic properties. The approach resolves longstanding challenges in assigning coherent prior probabilities to logical statements, including self-referential claims, using a criterion motivated by the impossibility of exploiting the algorithm via stock trading strategies. All desirable properties—including timely pattern learning, calibration, and dominating universal semimeasures—follow from a single logical induction criterion.

Key Points

• •Provides a computable algorithm assigning coherent probabilities to all statements in formal languages like Peano arithmetic, including self-referential beliefs and undecidable claims.
• •Learns patterns in logical truth values in polynomial time, even before having resources to directly evaluate statements.
• •Avoids standard self-reference paradoxes while achieving accurate beliefs about the algorithm's own current probability assignments.
• •All desirable properties derive from one unified logical induction criterion, framed as resistance to exploitation by polynomial-time trading strategies.
• •Relevant to AI safety as it provides foundations for bounded, self-aware reasoning agents with coherent probabilistic beliefs under computational constraints.