ABSTRACT
Algorithmic probability of a string s is the probability of that particular string being produced as the output of a reference universal Turing machine with random input. It is approximately 2- 1(p), where l(p) is the length of the shortest program p that will produce s as output. l(p) is the Kolmogorov complexity of s—one form of algorithmic complexity. The application of algorithmic complexity was to devise a formal theory of inductive inference. All induction problems are equivalent to the problem of extrapolating a long sequence of symbols. The problems solvable by the system fall in two broad classes: machine inversion problems and time-limited optimization problems. In both, the problem itself, as well as the solution, can be represented by a finite string of symbols. Almost all problems in science and mathematics can be well approximated or expressed exactly as either machine inversion problems or time-limited optimization problems.
