Equivalence of random coinflips view and minimal programs view

Two of the several ways of viewing the deterministic variant of Solomonoff induction are:

• The "random coinflips view": Given a monotone Turing machine, we feed the machine with random data (such as from unbiased coinflips). The probability of string $x$ is then the probability that the machine outputs something starting with $x$.
• The "minimal programs view": Given a monotone Turing machine $T$, the minimal programs producing $x$ are those programs $p$ such that $T(p)=x*$ (i.e. $T$ when run with $p$ produces an output starting with $x$) and such that no proper prefix of $p$ produces $x$ (i.e. if $q\prec p$ then $T(q)\neq x*$). This view then says that to get the probability of $x$, we add up all the minimal programs weighted by length as follows: for each program $p$ we assign the weight $2^{-|p|}$, where $|p|$ is the length of $p$. Thus the measure is $\sum _{p}2^{-|p|}$, where the sum is taken over all minimal programs $p$ producing $x$.

These two views turn out to be equivalent in the sense that .