Solomonoff Induction

Main Idea

Ok, here’s what I’ve gathered about Solomonoff Induction from what I’ve read:

  1. All states of the universe can be represented by bits, thus all observations can be represented as a set of bits.
  1. All hypotheses are algorithms.
  1. Algorithms are Turing Machines.
  1. A Turing Machine can be represented by a set of bits.
  1. A Universal Turing Machine can take any Turing Machine as input and produce an output set of bits.
  1. A Universal Turing Machine can take every possible Turing Machine and see which ones produce a given observation as output. This produces a set of Turing Machines that produce the given output. In other words, this produces the set of hypotheses that successfully explain an observation.
  1. The relative probabilities of these hypotheses can be calculated using their lengths (assuming 50% probability each bit goes either way, probability of a given hypothesis = $(\frac{1}{2})^n$ where $n$ is the number of bits in the hypothesis, this result is not normalized, but can be compared relatively with other hypotheses). This is the Solomonoff formalization of Occam’s Razor (i.e. Kolmogorov complexity).
  1. This way Solomonoff Induction provides precise probabilities for all hypotheses that explain an observation.

Relationship to Bayes’ Theorem

From what I understand right now, Solomonoff Induction is a brute force style expansion on Bayes’ Theorem that overcomes the problem of having to have correct priors while still providing correct probabilities of all possible explanatory hypotheses.

Implications

If Solomonoff Induction allows us to find the probabilities of all possible explanations of the truth, then discovering truth has been solved at the theoretical level. It is essentially incomputable (because of the enormous number of possible hypotheses, their lengths, and because of the Halting problem). But it does provide a groundwork for eventual efficiencies to make this truth finding computable. Universal Artificial Intelligence would be the creation of an efficient, usable truth finding computer using some method that provides an estimation of Solomonoff Induction.