 Credits 2 Points
 Lecturer Professor Cristian S. Calude, Room 253, ext 5751,
cristian@cs.auckland.ac.nz

With the cooperation of Dr. Richard Coles, Room 116, ext 7595,
r.coles@cs.auckland.ac.nz
 Duration Second semester 1998

Lecture Room cs 246
 Short Description
Algorithmic information theory (AIT) is the result of putting
Shannon's information theory and Turing's computability theory into a
cocktail shaker and shaking vigorously says
G. J. Chaitin, one of the
founders of this theory.
 AIT is relevant for:
 Logic: a
new light on Gödel's incompleteness phenomenon is obtained by
analyzing the informationtheoretic power of axiomatic systems
 Physics:
a characterization of chaotic physical motion

Biology: How likely is life to appear and evolve? How common is life in
the Universe?
 Metaphysics: Is the Universe ordered, rational or
random?
 Textbook and Recommended Reading
 C. Calude. Information and Randomness. An
Algorithmic Perspective, SpringerVerlag, Berlin, 1994 (textbook)

G. J. Chaitin. InformationTheoretic Incompleteness,
World Scientific, Singapore, 1992

G. J. Chaitin.
An invitation to Algorithmic Information Theory, in
D. S. Bridges, C. Calude, J. Gibbons, S. Reeves, I. Witten (eds.).
Combinatorics, Complexity, Logic, Proceedings of DMTCS'96, SpringerVerlag,
Singapore, 1996.

G. J. Chaitin.
The Limits of Mathematics SpringerVerlag, Singapore, 1997.

Chaitin's Home Page
 Steven Finch's Home Page on
"Favorite Mathematical
Constants" Chaitin's Constant

J. Barwise, J. Etchemendy. Turing's World 3.0. An Introduction to
Computability Theory, CSLI Lecture Notes 35, 1993
 Organization During the course students will work on several
assignments and will present a seminar on some AIT topic,
based on relevant "fresh" papers and/or books
 Assessment Assignments and seminar: 30%, Exam: 70%
 Seminar Topics
 Adapt
Chaitin software for the Macintosh

Relate Chaitin complexity of a program to its time complexity and
develop an application
 Construct
Chaitin's exponential Diophantine equation in your "model" of AIT

Develop an application of AIT in Physics (reversible computation, information
distance, thermodynamics, quantum computation)
 Develop an application of AIT in Biology (chaos vs predictability in
for biological systems)

Develop an application of AIT in
Philosophy (ChurchTuring's Thesis, mindbrainscomputers)

Develop an application of AIT in Logic (the incompleteness phenomenon,
inductive reasoning)

Explore the relevance of the size of the alphabet for coding
different computations

Open problems in AIT
 For queries or related matters send an
email