What isAlgorithmic Probability
Algorithmic probability is a mathematical framework that attempts to formalize Occam's razor. It assigns a prior probability to a hypothesis based on the length of the shortest program that can generate it on a universal Turing machine. Shorter programs are favored, reflecting the principle that simpler explanations are more likely to be true.
In essence, it provides a way to quantify the likelihood of different explanations or models for observed data, favoring those that can be described most concisely.
Key Concepts
- Kolmogorov Complexity: The length of the shortest program that produces a given string or hypothesis.
- Universal Turing Machine (UTM): A theoretical computing machine capable of simulating any other Turing machine. The specific UTM used affects the absolute algorithmic probability, but not the relative probabilities between hypotheses.
- Occam's Razor: The principle that, among competing hypotheses, the one with the fewest assumptions should be selected.
P(hypothesis) ≈ 2^(-K(hypothesis))Where P(hypothesis) is the algorithmic probability of the hypothesis and K(hypothesis) is its Kolmogorov complexity.
Algorithmic probability is uncomputable in general, as determining the shortest program for an arbitrary output is an undecidable problem. However, it provides a theoretical foundation for reasoning about uncertainty and model selection.