Logical induction

Abstract

This paper introduces a computable algorithm called a “logical inductor” that assigns probabilities to logical statements in a formal language, refining them over time. This algorithm learns to predict patterns of truth and falsehood in logical statements, even when lacking the resources for direct evaluation. It also learns to utilize appropriate statistical summaries for sequences with seemingly random truth values and develops accurate beliefs about its own beliefs, avoiding self-reference paradoxes. The logical inductor’s learning process is guided by a criterion inspired by stock trading analogies, ensuring that no polynomial-time trading strategy can achieve unbounded profits. This criterion resembles the “no Dutch book” principles underlying expected utility and Bayesian probability theories, providing a strong foundation for the algorithm’s behavior.