# On the Computability of Solomonoff Induction and Knowledge-Seeking

arXiv: https://arxiv.org/abs/1507.04124 · HTML: https://mlsanity.com/paper/1507.04124/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2015.

## Built on by (most cited first, 2 of 2)

- [Solomonoff induction](https://mlsanity.com/paper/2603.20274/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

Solomonoff induction is held as a gold standard for learning, but it is known to be incomputable. We quantify its incomputability by placing various flavors of Solomonoff's prior M in the arithmetical hierarchy. We also derive computability bounds for knowledge-seeking agents, and give a limit-computable weakly asymptotically optimal reinforcement learning agent.