How to extend Solomonoff's universal prior to stochastic models? Solomonoff's universal prior for models is based on the algorithmic complexity of a computer program $p$ which executes that model. Where $l$ is the length of the computer program, the prior is proportional to $2^{-l}$.
This works fine for deterministic models. We have an observation and we want to understand what model best explains the observation. If the program $p$ returns an output equal to the observation then this program is valid, otherwise it is invalid. We can apply Bayes rule to get a posterior probability by considering all programs which returned the desired output.
I'm confused about how this is extended to the case where there is randomness in the observations we collect.
Take a simple example: Suppose we are considering a linear regression model $y=ax+b$. The computer program which executes this model has a length $l$ which is a function of $a$ and $b$ (bigger parameters require more bits to model). The prior is $\pi(a,b)$.
But this program doesn't include a random element. The regression model is $y=ax+b+\epsilon$ where $\epsilon$ is random noise with a distribution $N(0,\sigma^2)$
How should we consider a prior for the noise? A computer program can't produce a random noise so this can't be a part of the program length. Should the prior for $\sigma^2$ be considered separately to the prior for the model? Or should the number of bits required to encode the numeric value $\sigma^2$ be included in the length of the program?
In addition to the variance of the noise, the underlying normal distribution would seen to have some degree of complexity associated with it. Should the bits required to describe a normal distribution be included in the model prior?
 A: 
If the program $p$ returns an output equal to the observation then this program is valid, otherwise it is invalid

My understanding of Solomonoff's prior is that each program $p$ does not generate an observation, nor is the prior over programs. Such a formulation would be crippled by the fact that there are only countably many programs, but uncountably many binary strings, so any prior assembled this way would end up assigning $0$ probability to all perfectly valid but uncomputable binary strings.
Rather, our hypothesis space is all possible (enumerable) semi-measures $\mu$ over all finite and infinite binary strings. $\mu$ is almost like a probability distribution but not quite.
The prior $P(\mu)$ is a prior over all enumerable semi-measures. However, it's quite difficult to have a prior over something as abstract as an enumerable semi-measure. Therefore, we consider programs $p$ such that when fed into a universal turing machine $U$, $U(p, x)$ computes $\mu(x)$. 
To make this less abstract, imagine $U$ being the a compiler and the underlying hardware, $p$ to be some code which computes the pdf of the normal distribution, and $\mu$ to be the normal distribution itself. This analogy breaks down because the support of $\mu$ is all finite and infinite binary strings.
Finally the prior is $P(\mu) = 2^{-l(p)}$. But not quite, because there may be many programs $p$ such that $U(p,x)$ computes $\mu(x)$. Therefore the actual prior is $P(\mu) = \sum_{p\ : \ U(p,x) = \mu(x)} 2^{-l(p)}$. A common approximation is to take $P(\mu) = 2^{-H(\mu)}$ where $H(\mu)$ is the length of the shortest valid $p$. Of course, there is no guarantee that any such valid $p$ exists, which is why prior is only over enumerable (computable) semi-measures. 
To return to your question, since programs correspond to semi-measures on binary strings, the ability to model stochastic data is built-in already. Returning to our analogy with the normal distribution, the complexity of the normal distribution and its parameters is taken into account by the universal prior by considering the length of the program(s) $p$ which compute it.
