Stationary Algorithmic Probability

Abstract

Kolmogorov complexity and algorithmic probability are conventionally defined relative to a universal reference computer, introducing an inherent machine-dependence. This dependence may be mitigated by assigning algorithmic probabilities to the computers themselves, based on the principle that unnatural computers are more difficult to emulate. Modeling universal computers as a Markov process of random emulations reveals that a stationary distribution—which would provide a machine-independent measure—does not exist for the set of all universal computers. The process is transient, a result with a physical interpretation suggesting that the elimination of additive constants is fundamentally impossible. Nevertheless, restricting the domain to specific subclasses of computers can produce positive recurrent processes. In these cases, stationary computer and string probabilities emerge with consistent symmetry properties and a direct relationship to weighted output frequencies. Ultimately, the persistence of ambiguity under output permutations confirms that machine-dependence is an irreducible feature of algorithmic information theory, reflecting the arbitrary nature of encoding schemes in physical descriptions. – AI-generated abstract.