Calculating Kolmogorov complexity from the output frequency distributions of small Turing machines
Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the traditional lossless compre...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Public Library of Science
2014
|