• 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