display | more...

Gregory Chaitin gave this as an example of a definable number, which is not computable; so you can describe a number which you will never be able to calculate... The obvious (and in a sense only) way to do this is to make the number's definition talk about the halting problem.

The number Ω is loosely defined as the probability of a randomly-generated Turing Machine (with input) ever halting. To make this precise, we pick a binary prefix-free encoding of all pairs of (syntactically) valid Turing Machines and inputs; this is not hard to do, just not very interesting. Equivalently, we consider all (binary encoded) programs for a Universal Turing Machine. We now pick successive bits with even probability, until we get a valid machine and input pair. If there are invalid strings in our representation, we just force the value whenever one choice would leave us with no valid continuation, but really we could just remove them from our encoding. The probability of the result halting is Chaitin's constant (for our chosen encoding).

Given sufficiently many digits of Ω, you could decide whether a given Turing Machine halts, thus answering the question of the halting problem; hence, the number must be uncomputable. Again, the specifics aren't all that exciting. You basically add the TMs one by one to your list (by length), and use an approximate value of Ω to decide whether they halt or not. You never need the exact value, because the shorter TMs have a greater effect on this number than all the longer ones put together (because of the prefix-free encoding we picked).

Ω is definable. It's not too hard to convince yourself of this, but actually spelling out the formula is rather wearisome. Some of Chaitin's fame stems from bothering to do this.

This number depends on the exact encoding chosen, but then (for this reason, amongst others) nobody really cares what it actually equals. (Well, some people calculated 60-odd places for a particular encoding, but this seems daft to me). The only point was to find a non-computable number in the definable numbers.

Log in or register to write something here or to contact authors.