Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness
详细信息 查看全文
- 作者：Jean-Paul Delahaye ; Hector Zenil
- 关键词：Algorithmic probability ; Algorithmic (program-size) complexity ; Halting probability ; Chaitin&rsquo ; s ¦¸ ; Levin&rsquo ; s universal distribution ; Levin&ndash ; Chaitin coding theorem ; Busy Beaver problem ; Kolmogorov&ndash ; Chaitin complexity
- 刊名：Applied Mathematics and Computation
- 出版年：2012
- 出版时间：15 September, 2012
- 年：2012
- 卷：219
- 期：1
- 页码：63-77
- 全文大小：350 K
文摘
We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic Kolmogorov-Chaitin complexity of all bit strings up to 8 bits long, and for some between 9 and 16 bits long. This is done by an exhaustive execution of all deterministic 2-symbol Turing machines with up to four states for which the halting times are known thanks to the Busy Beaver problem, that is 11 019 960 576 machines. An output frequency distribution is then computed, from which the algorithmic probability is calculated and the algorithmic complexity evaluated by way of the Levin-Chaitin coding theorem.