Relationship To The Halting Problem
Knowing the first bits of, one could calculate the halting problem for all programs of a size up to . Let the program for which the halting problem is to be solved be N bits long. In dovetailing fashion, all programs of all lengths are run, until enough have halted to jointly contribute enough probability to match these first N bits. If the program hasn't halted yet, then it never will, since its contribution to the halting probability would affect the first N bits. Thus, the halting problem would be solved for .
Because many outstanding problems in number theory, such as Goldbach's conjecture are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be.
Read more about this topic: Chaitin's Constant
Famous quotes containing the words relationship to the, relationship, halting and/or problem:
“Film music should have the same relationship to the film drama that somebody’s piano playing in my living room has to the book I am reading.”
—Igor Stravinsky (1882–1971)
“If the relationship of father to son could really be reduced to biology, the whole earth would blaze with the glory of fathers and sons.”
—James Baldwin (1924–1987)
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)