2009/11/23 by Bruno Bauwens, Bauwens, Bruno
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.0911.4521
25 pages
arxiv created 2009/11/23 · openalex publication_date 2009/11/23 · arxiv updated 2009/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is shown that the length of the algorithmic minimal sufficient statistic of a binary string x, either in a representation of a finite set, computable semimeasure, or a computable function, has a length larger than the computational depth of x, and can solve the Halting problem for all programs with length shorter than the m-depth of x. It is also shown that there are strings for which the algorithmic minimal sufficient statistics can contain a substantial amount of information that is not Halting information. The weak sufficient statistic is introduced, and it is shown that a minimal weak sufficient statistic for x is equivalent to a minimal typical model of x, and to the Halting problem for all strings shorter than the BB-depth of x.