# Find probability of non-stationary inputs into Turing machine?

Consider some finite string $$x=(x_1,x_2,...,x_{n-1},x_n)$$ that is drawn from a non-stationary process. Would it be possible to use the algorithmic probability formula, defined by Solomonoff as, $$P_M(x)=\sum_{i=1}^{\infty}2^{-|s_{i}(x)|}$$ to predict $$x_n$$, by computing the probability $$P_M(x_n | x_1,...x_{n-1})=P_M(x_1,x_2,...,x_{n-1},x_n)/P_M(x_1,x_2,...,x_{n-1})$$? Or is it a necessity that the process that $$x$$ is drawn from be stationary?

Edit: Here $$s_i(x)$$ refers to the $$i$$-th program which generated $$x=(x_1,x_2,...,x_{n-1})$$ and we want to predict the probability that $$x_n$$ is either a $$1$$ or a $$0$$.

• Interesting, but I'm a bit confused. I mean, I can use any probability to predict anything. So are you asking whether it's a good idea or not? That depends where $x$ comes from. But this feels philosophical ... also, it's not computable, so in that sense, I think "no, not possible". – usul Apr 5 '19 at 12:52
• @litmus I think your question shows some confusions. First, I believe you are using $s_i(x)$ to refer to the $i$-th program which generates $x$, which should be explained. Second, it is not $s_i(x)$ that has a universal distribution, rather the "universal distribution" is $P_M$ itself, as defined above. Lastly, it is not clear what you mean by a "non-stationary binary string". Usually a random process (i.e., a distribution over infinite strings) is said to be is stationary or not stationary, not a particular finite string. – Artemy Apr 6 '19 at 19:56
• @Artemy Hello again Artemy! Thank you for the comments, I have updated the question. – litmus Apr 6 '19 at 20:19
• That helps but I might still not be entirely understanding your question. The equation you have states exactly how to compute (or, more specifically, lower semicompute) $P_M(x)$ for any finite string $x$. Are you asking whether it is allowed for $x$ to be sampled from some non-stationary random process, say with distribution $Q$? If so, then yes -- the above probability measure is defined for any finite string whatsoever. – Artemy Apr 7 '19 at 0:06
• @Artemy Yes, that is exactly what I wanted to know, thanks! If you want to elaborate your comment as an answer instead, I'd be very happy to accept it. Also, please feel free to edit my question if you think that there are some parts that could be more clear for posterity. – litmus Apr 8 '19 at 14:49

The equation you have for algorithmic probability states how to compute (or, more specifically, lower semicompute) $$P_M(x)$$ for any finite string $$x$$, so it can also be used to predict $$x_n$$ by evaluating $$P_M(x_n \vert x_1, \dots , x_{n-1})$$. It holds for any finite string $$x$$ -- it does not matter what distribution (if any) $$x$$ is drawn from.