Primitive Kolmogorov complexity is computable

• The uncomputability of and Solomonoff induction
• Primitive recursive functions: a computable subclass
• Defining computable complexity and prediction
• The limits of the primitive recursive class
• is sufficient for real-world intelligence

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 a function's time complexity is bounded by a primitive recursive function of its input size, then the function itself is primitive recursive.

This class includes most functions and common algorithms encountered in computer science. Standard mathematical operations like addition, multiplication, and exponentiation are primitive recursive. Common algorithms whose operations are bounded by the input size - such as bubble sort and insertion sort, or graph algorithms like Dijkstra's - are primitive recursive.

Defining computable complexity and prediction #

Using this restricted class of functions, we can define computable versions of and Solomonoff induction:

• Primitive Kolmogorov complexity (): The of an object , or , is the length of the shortest primitive recursive program that produces it. The search for this shortest program is now a computable operation, as we only consider programs that are guaranteed to halt.

• Primitive Solomonoff induction: A computable predictor can be formulated by restricting the Solomonoff prior to the space of primitive recursive functions. The predictor would consider only the primitive recursive programs that could generate a given sequence, weighting them according to their length.

The limits of the primitive recursive class #

The restriction to primitive recursive functions means that certain total computable functions are excluded. The canonical example is the Ackermann function, a total computable function whose output grows faster than any primitive recursive function. For even small inputs, its value becomes computationally intractable.

The functions that lie outside the primitive recursive class are those characterized by such hyper-exponential growth. The practical limitations of using are therefore found in specific domains:

• Analysis of Hyper-Operations: The study of functions that grow at rates exceeding any standard exponential function.
• Complex Termination Proofs: Certain complex programs require non-primitive recursive functions to prove their termination within formal systems like Peano arithmetic.
• Worst-Case Analysis of Highly Complex Systems: Analyzing the absolute theoretical limits of certain algorithms or systems can involve non-primitive recursive complexity.

is sufficient for real-world intelligence #

The domains where primitive recursion fails are niche. For most practical applications in science and engineering, the functions required to model systems and make predictions are primitive recursive. The physical world does not appear to demand that intelligent agents compute non-primitive recursive functions to survive and operate effectively.

Whilst we might one day care about the sort of intelligence that is defined as a full "search over turing machines", for today's real world practical general intelligence, a "search over primitive recursive functions" is likely sufficient.

Therefore, is a more practically relevant framework for understanding intelligence and complexity in real-world systems than the uncomputable ideal of . While the theoretical uncomputability of is a foundational result, we should not build overarching conclusions from it about the limits of machine intelligence. The computable power of offers a viable and sufficient foundation for building and understanding intelligent systems.