CSci 301 Lecture Notes

Week Ten, Thursday: Definition of Information

The size of the shortest description (with a finite alphabet) determines the amount of information in a string.

Minimal Length Descriptions

The minimal description string contains an encoding of a Turing machine.

Optimality of the Definition

The definition of minimal length is shown to be optimal.

Incompressible Strings and Randomness

Incompressible strings of every length exist. The more order a string exhibits, the more compressible it is.

Homework Assignment

Assigned Thursday, November 12, due Thursday, December 3:

Chapter 6: Problems 6.7 and 6.9, due two weeks after the mid-term, Thursday, December 3.


Email: Richard dot J dot Wagner at gmail dot com

notes10b.htm, this hand crafted HTML file created August 31, 1998.
Last updated May 14, 2011, by Rick Wagner. Copyright © 1998-2011, all rights reserved.