Topic Three: Algorithmic
Information
Chaitin defines the information content of a
number ( or sequence of binary digits ) to be
the length of the shortest computer program
capable of generating that sequence.
He uses Turing machines as cannonical computers
Thus the information content of a sequence is the
shortest Turing machine tape that would cause the
machine to halt with the sequence on its output
tape.