**Algorithmic Information Theory**

“Randomness and Proof” is a nice, introductory-level article on

algorithmic information theory. It’s by G. J. Chaitin, who

has personally done a lot of the foundational work in this

area. A random, interesting snippet:

Solomonoff represented a scientist’s observations as a

series of binary digits. The scientist seeks to explain

these observations through a theory, which can be regarded

as an algorithm capable of generating the series and

extending it, that is, predicting future observations. For

any given series of observations there are always several

competing theories, and the scientist must choose among

them. The model demands that the smallest algorithm, the one

consisting of the fewest bits, be selected. Stated another

way, this rule is the familiar formulation of Occam’s razor:

Given differing theories of apparently equal merit, the

simplest is to be preferred.

Thus in the Solomonoff model a theory that enables one to

understand a series of observations is seen as a small

computer program that reproduces the observations and makes

predictions about possible future observations. The smaller

the program, the more comprehensive the theory and the

greater the degree of understanding. Observations that are

random cannot be reproduced by a small program and therefore

cannot be explained by a theory. In addition the future

behavior of a random system cannot be predicted. For random

data the most compact way for the scientist to communicate

his observations is for him to publish them in their entirety.

I’m writing a paper on Kolmogorov complexity for a class in complexity theory I’m taking this semester — if I get a chance, I’ll try to blog about some of the fascinating ideas in this field.

### Like this:

Like Loading...

*Related*