A circuit complexity formulation of algorithmic information theory

Cole Wyeth, Carl Sturtivant

Research output: Contribution to journalArticlepeer-review


Inspired by Solomonoff's theory of inductive inference (Solomonoff, 1964), 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 Universal Turing machine (UTM). There is one universal definition for Boolean circuits involving a universal operation (e.g. NAND) with simple conversions to alternative definitions (with 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.

Original languageEnglish (US)
Article number133925
JournalPhysica D: Nonlinear Phenomena
StatePublished - Dec 15 2023

Bibliographical note

Publisher Copyright:
© 2023 Elsevier B.V.


  • Algorithmic information theory
  • Boolean functions
  • Circuit complexity
  • Kolmogorov complexity
  • Sequence prediction
  • Solomonoff induction


Dive into the research topics of 'A circuit complexity formulation of algorithmic information theory'. Together they form a unique fingerprint.

Cite this