<p>It is computable.</p>
<p>Although <span class="math-container">$M$</span> is incomputable, since <span class="math-container">$M(x)\sim 2^{-K(x)}$</span>, the sequence <span class="math-container">$\omega$</span> generated by <span class="math-container">$argmax M$</span> would have quite low Kolmogorov complexity.</p>
<p>If the sequence is generated by <span class="math-container">$argmin M$</span>, then it would be Martin-lof random.</p>

CC BY-SA 4.0
2021-04-13T05:17:16.570Z
2021-04-13T05:17:16.570Z
Xi Li
<p>Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$. </p>

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

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

<p><strong>UPDATE</strong></p>

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

<p>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?</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-23T01:27:23.167Z
Yes, for example, ties are be broken in favor of zero.
Gleb
<computability><randomness>
What kind of string is produced by successive application of argmax M
Gleb
# What kind of string is produced by successive application of argmax M

(Asked by: username_0 on 2013-08-22)

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.

**Tags:** computability, randomness

> **Comments:**
> **username_0**: Yes, for example, ties are be broken in favor of zero.  

---

## 1 answers

### Answer by username_1 on 2021-04-13. Score: 0

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.


---

