A Circuit Complexity Formulation of Algorithmic Information Theory
Cole Wyeth Carl Sturtivant
Inspired by Solomonoffs theory of inductive inference, we propose a prior
based on circuit complexity. There are several advantages to this approach.
First, it relies on a complexity measure that does not depend on the choice of
UTM. There is one universal definition for Boolean circuits involving an
universal operation such as nand with simple conversions to alternative
definitions such as and, or, and not. Second, there is no analogue of the
halting problem. The output value of a circuit can be calculated recursively by
computer in time proportional to the number of gates, while a short program may
run for a very long time. Our prior assumes that a Boolean function, or
equivalently, Boolean string of fixed length, is generated by some Bayesian
mixture of circuits. This model is appropriate for learning Boolean functions
from partial information, a problem often encountered within machine learning
as "binary classification." We argue that an inductive bias towards simple
explanations as measured by circuit complexity is appropriate for this problem.