Algorithmic information theory

What Hacker News says

1. mahmudApr 2009
   The one for "LISP" is an idealized Lisp that's just a step above the pure, untyped lambda calculus. See Gregory Chaitin's Algorithmic Information Theory for a slightly more detailed implementation of an ancient but pure Lisp.
   thread
2. trompApr 2025
   > it is a function about Turing machines, which is how the BBF gets the special properties/results that it does.

   The properties of the Busy Beaver function carry over to any other computational model you could base it on. E.g. the lambda calculus based BBλ[1] shares most of its properties.

   > Which immediately reminds me of Chaitin's constant which also tries to encode/talk about the properties of Turing machines,

   Chaitin's work on Algorithmic Information Theory (aka Kolmogorov Complexity) was actually focussed on custom Lisp languages of his own design rather than Turing Machines. One could be confused though by some of his articles on LISP program-size complexity like [2] where he calls his LISP interpreter a UTM (Universal Turing Machine).

   [1] https://oeis.org/A33347

   [2] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...

   Show morethread
3. guiraldelliMay 2016
   The standard reference is "An Introduction to Kolmogorov Complexity and Its Applications", from Ming Li and Paul Vitányi. It is the "must-go" for the subject.

   An introductory chapter is available in the "Elements of Information Theory" of Thomas Cover and Joy Thomas.

   The field is called "Algorithmic Information Theory" and some of the big names in it are: Ray Solomonoff, Gregory Chaitin, Ming Li, Paul Vitányi, Chris Wallace, David Dowe, Markus Hutter, Jürgen Schmidhuber, Jorma Rissanen, among others. All of these guys are great writers and have breakthrough ideas!

   If you are interested in "real world" applications of Kolmogorov complexity, I recommend you to take a look at MDL (Minimum Description Length) and MML (Minimum Message Length).

   I hope you will enjoy the references! :)

   Show morethread
4. fogusSep 2010
   I wrote a review of Chaitin's Algorithmic Information Theory a couple of years ago. I talk briefly about his approach in using Lisp. http://blog.fogus.me/2008/12/19/bookpr0n-0-gregory-chaitins-...
   thread