Computer Science – Information Theory
Scientific paper
2006-08-25
Theoretical Computer Science 411 pp. 113-130 (2010)
Computer Science
Information Theory
13 pages, 5 figures. Added an example of a positive recurrent computer set
Scientific paper
Kolmogorov complexity and algorithmic probability are defined only up to an additive resp. multiplicative constant, since their actual values depend on the choice of the universal reference computer. In this paper, we analyze a natural approach to eliminate this machine-dependence. Our method is to assign algorithmic probabilities to the different computers themselves, based on the idea that "unnatural" computers should be hard to emulate. Therefore, we study the Markov process of universal computers randomly emulating each other. The corresponding stationary distribution, if it existed, would give a natural and machine-independent probability measure on the computers, and also on the binary strings. Unfortunately, we show that no stationary distribution exists on the set of all computers; thus, this method cannot eliminate machine-dependence. Moreover, we show that the reason for failure has a clear and interesting physical interpretation, suggesting that every other conceivable attempt to get rid of those additive constants must fail in principle, too. However, we show that restricting to some subclass of computers might help to get rid of some amount of machine-dependence in some situations, and the resulting stationary computer and string probabilities have beautiful properties.
No associations
LandOfFree
Stationary Algorithmic Probability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Stationary Algorithmic Probability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stationary Algorithmic Probability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-111356