2
$\begingroup$

Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$.

Start with some $\omega_0$. Each subsequent element is given by $\omega_n=\arg \max_a\mathbf M(a|\omega_{1:n-1})$.

What are the properties of $\omega$? For example, is it necessarily computable? Does the answer depend on the choice of $\mathbf M$?

UPDATE

The equivalent formulation is the following but it does not really help me advance with the problem.

Is there a universal lower semicomputable $\lambda$-supermartingale $t$ and a binary sequence $\tilde\omega$ such that $t$ always "goes up" along $\tilde\omega$ but never succeeds?

This type of problem arises when a player plays against a reactive environment and the sequence the player observes is not exogenous. A more general question is what is the short-run behavior of $\mathbf M$ since asymptotic results do not seem to help here.

$\endgroup$
2
  • $\begingroup$ Would ties be broken in favor of zero? $\;$ $\endgroup$
    – user6973
    Commented Aug 23, 2013 at 0:47
  • $\begingroup$ Yes, for example, ties are be broken in favor of zero. $\endgroup$
    – Gleb
    Commented Aug 23, 2013 at 1:27

1 Answer 1

0
$\begingroup$

It is computable.

Although $M$ is incomputable, since $M(x)\sim 2^{-K(x)}$, the sequence $\omega$ generated by $argmax M$ would have quite low Kolmogorov complexity.

If the sequence is generated by $argmin M$, then it would be Martin-lof random.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.