10 ms·
Is there a prose explanation or justification for Algorithm Information Theory. I think I first heard of it when I saw your IOCCC entry, but I was never able t
by Verdex_3 8y ago
Is there a prose explanation or justification for Algorithm Information Theory. I think I first heard of it when I saw your IOCCC entry, but I was never able to get my mind wrapped around what the goal of the whole field was.
- antidesitter 8y agoThe goal of AIT is to study the complexity of mathematical objects as defined through models of computation.
- jkabrg 8y agoI guess it provides an objective definition of when something is simple or complicated. This could have applications in statistics or machine learning, where "simpler" hypotheses could be less likely to overfit. There are computable measures of "simplicity" (unlike Kolmogorov complexity) based on compression algorithms or computation time (Levin complexity). There are also apparently connections to statistical mechanics, but I haven't looked into it and I don't know if it's useful. See this paper on how to cluster using compression: https://arxiv.org/pdf/cs/0312044.pdf https://arxiv.org/pdf/cs/0312044.pdf