- 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 information-theoretic 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, Springer-Verlag, Berlin, 1994 (textbook)
-
G. J. Chaitin. Information-Theoretic 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, Springer-Verlag,
Singapore, 1996.
-
G. J. Chaitin.
The Limits of Mathematics Springer-Verlag, 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 (Church-Turing's Thesis, mind-brains-computers)
-
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