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?



A modern tweak on algorithmic information theory is 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, Theory Comput. Syst. 46, No. 3, 598-617 (2010). ZBL1204.68110..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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