Wednesday, February 08, 2006

How to Run Algorithmic Information Theory on a Computer

I missed this talk.
Algorithmic Information Theory is recursive function theory plus program complexity.
Chaitin wants to have a real programming language (pure LISP with some enhancements) and a real computer (a particular Universal Turing Machine) and then actually do real stuff, like list out all possible theorems and score them...
LISP is enhanced with a handful of functions. Most importantly, try
(try time-limit expression binary-data).
What this does is evaluate the expression on the data and return at the earlier of when the evaluation is complete or time-limit is exceeded.