Chaitin gave a not very formal but very nice and informative talk about omega at CMU in 200. Here is part 1 (the other parts should be easy to find).

http://www.youtube.com/watch?v=HLPO-RTFU2o

Someone above asked if this is just a restatement of Kolmogorov complexity. I'm not good enough at the technical details to say precisely yes or no but, basically: "yes" - they are regarded as simultaneous and independent discoveries. Kolmogorov complexity is also sometimes called Kolmogorov-Chaitin complexity.

-t

Thanks for the video, I will watch it. The interested readers might want to try the book "An Introduction to Kolmogorov Complexity and its Applications" by Li and Vitanyi (the 3rd edition came out recently). It is comparatively expensive, but Vitanyi's CWI site holds additional material.

Also, keep in mind that it's not just a result about programming / halting problem. It has implications for the foundations of mathematics. For example, if you formalize math such that you can measure the bit-length of theorems about numbers, you'll find that in the limit, to have a theory of all true theorems up to length N-bits, you'll need O(N) bits of axioms. (I'm probably not saying that in the best possible way: again, I'm no technician in these matters.)

My highschool math teacher spent two classes proving Goedel's incompleteness theorem to us, so this was really cool to see in programming form.

Besides that though, I finally understand what LISP is all about. I've never worked with LISP before, and his explanation of LISP as manipulating sets blew my mind!

Does anyone have any LISP tutorials they recommend? I did a quick search and came up with loads, but it's hard to tell if they're good right off the bat.

MIT's Structure and Interpretation of Computer Programming is in LISP (Scheme to be exact) All the lectures and course materials are under Creative Commons.

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...

I can't believe I didn't think of OpenCourseWare. Thanks!

Not to pg-fanboy out too much, but I really like his ANSI Common Lisp: http://www.paulgraham.com/acl.html . It's not the newest thing on the market, but is quite good. Obviously, it's a book, so you'd have to buy or borrow it. Also, Arc has a tutorial online: http://ycombinator.com/arc/tut.txt

There was a concerted effort by Lispers a year or two ago to get it so that Peter Seibel's book would come up first if you Google for "lisp tutorial". I believe it still does, and it's very good.

After a cursory glance this just looks like a restatement of Kolmogorov Complexity: "...the complexity is the length of the string's shortest description in some fixed universal description language."

Traditionally a Turing Machine is used as the fixed universal description language. This paper just substituted scheme.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

They are tied, but it is being restated by one of the independent discoverers of the concept. Furthermore the theorem he is talking about is original to him.

There is no "just" to it.

Ah, my mistake. I didn't read the dates on the link, and assumed it was recently created.

One of the conclusions you can draw from this that I love is that there are exponentially more complex things than there are simple things. The number of unique, 'elegant' programs short enough to store in 32 bits is 2^32, but the number of unique, 'elegant' programs you can store in 100 bits is 2^100.

Explain those estimates, please. And do recall that not all programs are elegant.

Not all programs representable by 32 bits are elegant, but of all programs that are both 32 bits long and elegant, there are no more than 2^32 of them.

edit: this follows from the uniqueness of each "elegant" program.

You post listed exact counts, not upper bounds.