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.