Talk:Chaitin's constant

From Wikipedia, the free encyclopedia

Contents 1 comments by exa 2 Shaitan's Consonant 3 On the probability interpretation 4 Merge 5 Properties of Chaitin's constant 6 rewrite

[edit] comments by exa

It is a normal and transcendental number which can be defined but cannot be computed

I really doubt that this fact is proven yet. Both (the normalness and the transcendence) is quite likely, but I have never seen a proven for either of that. I would be surprised if the irrationality of the number is already proven, which I doubt again due to the incomputableness of the number.

(The constant N heavily depends on the encoding choices and does not reflect the complexity of the axiomatic system in any way.)

Where did you get this terrible idea?.... Do you know the invariance theorem? Do you know Theorem C in AIT that shows the relation between the axiomatic complexity of a FAS to the number of digits that can be proven? exa 16 Sep, 2004

... then there exists a constant N such that no digit of Ω after the N-th can be proven to be one or zero within that system.

Is this true? It seems like this states that there are at most a finite number of Turing machines that can be proven to either halt or not halt (given some system of enumeration, etc.). Chas zzz brown 02:06 Feb 5, 2003 (UTC)

Ooops! In the words of emily latella, "never mind". I misread that the nth digit of Ω was 1 iff Turing machine n halts. Chas zzz brown 09:00 Feb 5, 2003 (UTC)

The proof of the transcendence of Chaitin's number for any particular encoding could rely on the following indirect argument. If Chaitin's number is algebraic, then it is computable. But we can prove it isn't computable as this leads to a contradiction with the undecidability of the halting problem. However, does this argument hold water if Chaitin's number is algebraic, but it is absolutely impossible to determine which one it is? At 3am, I'm not sure... Elroch 02:11, 27 March 2006 (UTC)

I have rewritten the introduction to this article and added some headings to divide it into sections. I am not sure if this belongs to algorithmic information theory so perhaps someone can put it in the right category. MathMartin 17:44, 20 Jul 2004 (UTC)

What does the statement "Ω is uncompressible" mean? Is compressible number defined anywhere in the Wikipedia? - Mike Rosoft 16:55, 8 Dec 2004 (UTC)

Oops! I thought the link I had supplied to Data compression would clear it up. It means that it is impossible to supply a program + infinite "compressed" sequence such that for any n, the program can return the first n bits of Ω using the first f(n) bits of the compressed sequence, and for any k there exists n₀ such that for n > n₀, f(n) < n − k. I couldn't find this definition anywhere in the data compression category. Lev 20:15, 9 Dec 2004 (UTC)

I have included a summary of the definition for incompressible number. Rattle 09:00, 1 Jun 2005 (UTC)

Certainly there may be an algorithm that computes Chaitin's constant. There is just no way to prove that any algorithm does so.

Nope. If there were such an algorithm, it could be used to solve the halting problem (even though we would not be able to prove it). But there is no algorithm, provable or not, that solves it. – Lev 10:35, 10 August 2005 (UTC)

To clarify this a bit: There is no algorithm that computes ALL bits of Chaitin's constant. Otherwise, it could be used to solve the halting problem: We would try to compute Omega by running all possible programs in parallel (we would have to launch them one by one, of course). Then we would sum up 2^-(length) for every program that would terminate. Now one of two things would happen: either the prog in question would terminate, or the sum would eventually excede Omega-2^(-our prog's length), proving by contradiction that the answer is no.

Now if there were an algorithm for computing Omega but we didn't know which it was, the above meta-algorithm would give us an algorithm for solving the halting problem, but we still wouldn't know what it was. But there is no solution to the halting problem, not even one we can't find.

Certainly, for any finite N there is an algorithm that computes the first N bits of Omega, but we don't always know which it is. And there might (for all I know) be an algorithm that computes an infinite number of bits, but still leaves an infinite number of bits unknown.

Lev 12:33, 21 December 2005 (UTC)

I think the last remark here is wrong, or at least it contradicts to the last sentence of this article: from some N the digits cannot be computed algorithmically, i.e. the algorithm does not exist. From my experience with automatic theorem provers, I'd like to add a metaphor: the automated theorem proving can algorithmically prove quite a lot and help automate proving that certain algorithms do halt or do not halt, but at some (more complicated) point it needs human assistance. There are even more complicated problems than the halting problem, so the later numbers of Chaitin's constant will be even harder to compute.

Lev is right. For any finite N, you can just print out a string which happens to be the relevant bit of omega :). Beyond a certain N, you cannot prove that you are right, as the article states.

One candidate for an algorithm that produces an infinite number of bits is the program which starts simulating every Turing machine (cascaded, so that you're not trying to do an infinite number of things at once), and records those that halt. This machine can produce a sequence that limits to omega from below. IIRC, all of the `1's it produces are correct digits of omega. To prove that such a machine produces infinitely many bits of omega, it only remains to be shown that it keeps on producing 1s (I don't know if that can be done; it might depend on the model of computation/distribution of programs). -- pde 00:16, 14 March 2006 (UTC)

[edit] Shaitan's Consonant

I know what it is! Shaitan's consonant is 666! Repent, infidels!!! -ZyXoas (wiki user, not logged in).

Oooookay, then.

[edit] On the probability interpretation

The following two sentences don't agree; the first one doesn't make sense.

It can then be shown that Ω represents the probability that a randomly produced bit string will 
encode a halting program. This means that if you start flipping coins, always recording a head 
as a one and a tail as a zero, the probability is Ω that you will eventually reach the encoding of  
a syntactically correct halting program.

It is true that Omega is the probability that a randomly chosen infinite sequence of 0s and 1s begins with a string that is a halting program. This makes sense, because there is a probability measure (Lebesgue measure) on the set of such infinite sequences, and the set of sequences that begin with a string encoding a halting program is a measurable set. But there cannot be a randomly chosen bit string because there is no nontrivial probability measure on the set of finite bit strings. CMummert 04:37, 16 June 2006 (UTC)

Yeah, it shold be probability that randomly chosen infinite bit string begins with a proper program which stops after finite time.

I'm not sure will it make things more clear... But the way it is now is correct with some explanations. After all you can assume that you randomly chose bits of a string until (if ever) you reach a valid program string. In such random experiment probability of obtaining program that stops is exactly \Omega. Macieksk 09:28, 24 June 2006 (UTC)

[edit] Merge

The article "Omega (computer science)" is very similar to this one. I suggest that they be merged.P.L.A.R. 21:41, 29 June 2006 (UTC)

See my comments on the other article's discussion page. This page should stay, the other one should go, since this is not the only omega in use in computer science, and perhaps not even the most common. There doesn't seem to be much info on the current Omega (computer science) page that should be brought over here. --Dantheox 23:40, 29 June 2006 (UTC)

Omega (computer science) now redirects to this page.P.L.A.R. 21:00, 30 June 2006 (UTC)

[edit] Properties of Chaitin's constant

Shouldn't some reference be made to the fact that one can use Chaitin's constant to determine the answer to any possible phrasable question? Jenigmat429 03:16, 13 February 2007 (UTC)

That "fact" is not true. Chaitin's omega is at level Sigma_1 of the arithmetical hierarchy. Complete knowledge of it cannot even determine the truth of Pi_2 sentences of Peano arithmetic, much less more complicated questions. Chaitin's constant is Turing equivalent to the Halting problem, and nothing more. CMummert · talk 03:24, 13 February 2007 (UTC)

Ok, more accurately, couldn't you use it to determine the provability of a proposition L in a formal system F? Because, if there's a program that's sufficiently small that will halt if L is provable in F, and if you know enough of chaitin's constant, one could use Chaitin's omega to determine L's provability in F. Or maybe I'm interpreting Chaitin's omega wrong. Jenigmat429 14:16, 13 February 2007 (UTC)

Yes, you can use a Chaitin constant to do that. But this is because these constants are equivalent to the Halting problem, not in particular because of their randomness. CMummert · talk 16:56, 13 February 2007 (UTC)

[edit] rewrite

I expanded and rewrote the article this morning. Feel free to hack away at it, I'm done for a while. CMummert · talk 17:48, 13 February 2007 (UTC)