Abstract
We present a computable algorithm that assigns probabilities to every logicalstatement in a given formal language, and refines those probabilities overtime. For instance, if the language is Peano arithmetic, it assignsprobabilities to all arithmetical statements, including claims about the twinprime conjecture, the outputs of long-running computations, and its ownprobabilities. We show that our algorithm, an instance of what we call alogical inductor, satisfies a number of intuitive desiderata, including: (1) itlearns to predict patterns of truth and falsehood in logical statements, oftenlong before having the resources to evaluate the statements, so long as thepatterns can be written down in polynomial time; (2) it learns to useappropriate statistical summaries to predict sequences of statements whosetruth values appear pseudorandom; and (3) it learns to have accurate beliefsabout its own current beliefs, in a manner that avoids the standard paradoxesof self-reference. For example, if a given computer program only ever producesoutputs in a certain range, a logical inductor learns this fact in a timelymanner; and if late digits in the decimal expansion of $\pi$ are difficult topredict, then a logical inductor learns to assign $\approx 10\%$ probability to"the $n$th digit of $\pi$ is a 7" for large $n$. Logical inductors also learnto trust their future beliefs more than their current beliefs, and theirbeliefs are coherent in the limit (whenever $\phi \implies \psi$,$\mathbb{P}_\infty(\phi) \le \mathbb{P}_\infty(\psi)$, and so on); and logicalinductors strictly dominate the universal semimeasure in the limit. These properties and many others all follow from a single logical inductioncriterion, which is motivated by a series of stock trading analogies. Roughlyspeaking, each logical sentence $\phi$ is associated with a stock that is worth\$1 per share if [...]