<p>A modern tweak on algorithmic information theory is <a href="http://www.scholarpedia.org/article/Algorithmic_randomness" rel="noreferrer">algorithmic randomness</a> which was developed intensively in the 2000s (2009-2009) and is still quite active. </p>

<p>The most notorious open problem there may be whether <em>Kolmogorov-Loveland randomness</em> (in which martingales are computable but are allowed to bet on bits out of order) is the same as <em>Martin-Löf randomness</em> (in which martingales are only semicomputable, i.e., the capital function is computably approximable from below). This is known to be almost true, e.g. if <span class="math-container">$A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}$</span> is KL-random then either <span class="math-container">$A$</span> or <span class="math-container">$B$</span> is ML-random.</p>

<p>An example of a recent paper in this area:</p>

<p><em>Bienvenu, Laurent</em>, <a href="http://dx.doi.org/10.1007/s00224-009-9232-4" rel="noreferrer"><strong>Kolmogorov-Loveland stochasticity and Kolmogorov complexity</strong></a>, Theory Comput. Syst. 46, No. 3, 598-617 (2010). <a href="https://zbmath.org/?q=an:1204.68110" rel="noreferrer">ZBL1204.68110</a>..</p>

CC BY-SA 4.0
2018-10-14T19:30:20.250Z
2018-10-14T19:54:12.243Z
2018-10-14T19:54:12.243Z
Bjørn Kjos-Hanssen
<p>I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done before many years.</p>

<p>So my question is:
Is the field “alive” or is it pretty much closed? 
Does it have open questions? </p>

<p>Thanks</p>

CC BY-SA 4.0
2018-10-14T09:21:48.193Z
Maybe this can help: http://www.jucs.org/jucs_2_5/algorithmic_information_theory_open/Calude_C.pdf
Avi Tal
<cc.complexity-theory><it.information-theory>
Is algorithmic information theory still evolving?
Yovboy
# Is algorithmic information theory still evolving?

(Asked by: username_0 on 2018-10-14)

I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done before many years.

So my question is:
Is the field “alive” or is it pretty much closed?
Does it have open questions?

Thanks

**Tags:** cc.complexity-theory, it.information-theory

> **Comments:**
> **username_1**: Maybe this can help: http://www.jucs.org/jucs_2_5/algorithmic_information_theory_open/Calude_C.pdf  

---

## 1 answers

### Answer by username_2 on 2018-10-14. Score: 7

A modern tweak on algorithmic information theory is [algorithmic randomness](http://www.scholarpedia.org/article/Algorithmic_randomness) which was developed intensively in the 2000s (2009-2009) and is still quite active.

The most notorious open problem there may be whether *Kolmogorov-Loveland randomness* (in which martingales are computable but are allowed to bet on bits out of order) is the same as *Martin-Löf randomness* (in which martingales are only semicomputable, i.e., the capital function is computably approximable from below). This is known to be almost true, e.g. if $A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}$ is KL-random then either $A$ or $B$ is ML-random.

An example of a recent paper in this area:

*Bienvenu, Laurent*, [**Kolmogorov-Loveland stochasticity and Kolmogorov complexity**](http://dx.doi.org/10.1007/s00224-009-9232-4), Theory Comput. Syst. 46, No. 3, 598-617 (2010). [ZBL1204.68110](https://zbmath.org/?q=an:1204.68110)..


---

