Lambda the Ultimate

Greg Buchholz: So my next questions would be, "Has anyone actually calculated a specific Ω for a particular system?", and "What is the highest Ω could be for a universal machine?"

Well, Ω can't be computed, right? Anyway, that's precisely the subject matter of Exploring Randomness. See especially A more general framework---Special-purpose computers C, algorithmic probability P, and the halting probability Ω.

I'm not sure I understand what "What's the highest Ω could be for a universal machine?" means. If I understand Algorithmic Information Theory correctly, the Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy. But if you look at "Exploring Randomness," you'll find a universal machine in Chaitin's dialect of Lisp and you can calculate some arbitrary number of bits of Ω for the language of that universal machine. Is there an isomorphism from Ω for Chaitin's universal machine to Ω for any other universal machine? If I understand Chaitin correctly, the answer is "no," which is why I suspect that your question is not only unanswerable, but is not even well-formed.

Well, Ω can't be computed, right?

<snip>

...Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy.

I'm not sure I understand what "What's the highest Ω could be for a universal machine?" means.

Me: Well, Ω can't be computed, right?

...Ω for any given machine is essentially random, so there's no way to answer the question short of implementing the machine and computing bits of Ω until you're happy.

The apparent contradiction is resolved by making two observations:

1. Ω is a family of numbers that has to be instantiated for a particular machine, so of course talking about computing Ω without talking about what machine it's been "instantiated with," if you will, is meaningless. But this is a pretty vaccuous observation.
2. "Computing bits of Ω until you're happy" should be taken literally. As Chaitin writes, not only can you not compute all of Ω, you can't even determine how many of the "last bits" are wrong when you've stopped, or how many more bits you'd have to compute to get "close enough." "Computing N bits of Ω" is tantamount to tossing a fair coin N times!

Greg: Or writing programs for it would take just as much work as computing the answer itself. Hmm. More to ponder.

That's fundamentally where you wind up with Ω: strong irreducability, programs for computing things that are (must be!) as long as the thing they compute... I'm handwaving now, but you'd be better served by reading "Exploring Randomness" than by me feebly trying to explain further with any acceptable level of rigor.

You could maybe approach 1.0 by adding redundencies (like differing symbols which end up computing the same thing) and No-Ops. The machine with the lowest value for Ω would be the leanest, most compact universal machine possible, right?

You need to think a little harder about what you wrote. You could apply the exact same technique to raise Ω to lower it. Simply add infinite looping constructs to the language.

Of course, since programmers don't produce programs by flipping coins, I'm not really sure how valuable such a metric would be.

There are various automatic-program-generation techniques including genetic program which do in fact "flip coins" to generate programs. More or less.

Well, Ω can't be computed, right?

The general disclaimer: I have little knowledge of this field. ;-)

Uhm, your thread popped the up the following questions. Why? I mean: did he prove that it is impossible to analytically derive a specific Ω, in a mathematical sense, from the description of a machine? Is it an irrational number? Does he state anything about the Kolmogorov complexity of the program which computes Ω?

Yes. After all, Ω_C is just the probability that a randomly-chosen program for machine C will terminate. The definition alone should make clear that the number can't be computed; the trick is to prove it.

marco: Is it an irrational number?

By definition, I would think, but this is admittedly a guess.

Update: Leave it to MathWorld: "Ω_U is known to be a transcendental number."

marco: Does he state anything about the Kolmogorov complexity of the program which computes Ω?

Well, "The algorithmic information or Kolmogorov complexity of a bitstring x is the length of the shortest program that computes x and halts," and one of Ω's properties is that the program to generate it can't be any shorter than itself. So we can say that Ω has maximal Kolmogorov complexity.

Update: I see that I answered the wrong question, discussing the Kolmogorov complexity of Ω, which would trivially have to be maximal, vs. the Kolmogorov complexity of a program to compute N bits of Ω. I will have to return to this later.

Part I of "Exploring Randomness" goes into great detail: "Definition of the complexity H(x) of an S-expression x". This is in terms of a universal Turing machine defined in Chaitin's own dialect of Lisp that he developed to make these investigations easier (it has an M-expression syntax, time-limited evaluation, and explicit support for reading bit-strings). He then defines relative complexity and proves his results. You can find the Lisp code from "Exploring Randomness" here, and the Java, C, and Mathematica versions of his Lisp interpreter here.

There's also some interesting stuff here:

What if we allow for nonhalting computations on nonstandard Turing machines? It turns out that some things then become much more compactly describable. This leads to generalizations of the concept of Kolmogorov complexity, and has consequences for Solomonoff's theory of algorithmic probability and universal prediction. It also leads to "Super Omegas" that are computable in the limit - generalizations of Chaitin's halting probability Omega of a Turing machine with random input.

Thanks for the answers. Somehow, I find it an annoying definition. Then again, I guess I should give it some more thought first.

Greg Buchholz: I'll definitely read the book, but for us empirical guys, does anyone know if there is a machine for which at least a single bit of omega has been computed? If there has been, was Ω>0.5 or less than 0.5?

From AT&T's On-Line Encyclopedia of Integer Sequences, we find a few digits of Ω for some unspecified universal machine: 0.00787499699...

That is, for that universal machine, slightly less than eight out of every 1,000 randomly-chosen programs will terminate. IIRC, one of Chaitin's results is that for any universal machine, most programs won't terminate, i.e. "most things aren't computable."

Well, solve the problem and please become very rich ;-). I still ponder about it, when time permits.

Mr. Chaitin also has some insight into this question. From Elegant LISP Programs...

Call a program ``elegant'' if no smaller program has the same output. I.e., a LISP S-expression is defined to be elegant if no smaller S-expression has the same value.

and

So we've gotten an upper bound on the size of provably elegant LISP expressions. The upper bound is this: A formal axiomatic system whose LISP complexity is N cannot prove that a LISP expression is elegant if the expression's size is greater than N + 410. So at most finitely many LISP expressions can be shown to be elegant.