10
$\begingroup$

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

|cite|improve this question
$\endgroup$
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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