Primitive Kolmogorov complexity is computable

Summary

This post is mostly AI generated, of course with significant guidance, feedback, iteration and some edits from me. There was little for me to gain writing this myself, but I felt it needed to be written down regardless. Kolmogorov complexity and Solomonoff's theory of inductive inference offer formal, theoretical solutions to measuring complexity and forming predictions. However, both are uncomputable, a fact that is often treated as having significant implications in computability theory and artificial intelligence. I'm going to argue that by reformulating these concepts over the class of primitive recursive functions, we arrive at computable and practically relevant analogues: Primitive Kolmogorov complexity () and a primitive form of Solomonoff induction. The uncomputability of and Solomonoff induction # The Kolmogorov complexity of an object , denoted as , is the length of the shortest program on a universal Turing machine that outputs the object. Solomonoff induction uses this principle to assign a prior probability to a hypothesis based on its Kolmogorov complexity, creating a universal predictor. The uncomputability of both arises directly from the Halting Problem. To find the shortest program, one must be able to determine if any given program will halt. As this is impossible for all programs, and are not calculable. Primitive recursive functions: a computable subclass # The primitive recursive functions are a large and powerful subset of the total computable functions. A function is primitive recursive if it can be defined using only basic initial functions (such as the zero function, successor function, and projection functions) and a finite number of applications of composition and primitive recursion. A key property of this class is that every primitive recursive function is a total function - meaning it is defined for all inputs and is guaranteed to halt. This guarantee sidesteps the Halting Problem. A useful heuristic from complexity theory is that if ...