This lecture concerns algorithmic complexity theory, or Kolmogorov Complexity. The essential feature of this theory is: an object is no more complex than the shortest program that accurately describes it.

1. Review of Shannon's notion of entropy. Entropy in a communication channel translates to uncertainty in the values soon to be transmitted. This suggests that there is a current lack of information that will be satisified by the incoming message.
2. Notion of randomness: a system with high entropy. Hard to construct the exact state because all features appear unrelated.
3. A bit of programming.
   • Variables contain state. Numbers, booleans.
   • Assignment.
   • Basic computation.
   • Conditional statements. IF condition THEN statement.
   • Looping statements. WHILE condition DO statement.
   • Procedures.
4. Kolmogorov complexity: the shortest program that describes an object, determines its complexity.
   • Example. An amazing(ly simple) number.
   • Example. An amazing(ly complex) cell. Isn't DNA just a program?

Resources needed for next class:

• A reading about Life
• The Life Applet (for fun and experimentation!)

These items require Acrobat Reader.
These items require real player or windows media player
These items are Java applets, and require Java to be installed on your machine.