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, 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)
“It is possible to make friends with our children—but probably not while they are children.... Friendship is a relationship of mutual dependence-interdependence. A family is a relationship in which some of the participants are dependent on others. It is the job of parents to provide for their children. It is not appropriate for adults to enter into parenthood recognizing they have made a decision to accept dependents and then try to pretend that their children are not dependent on them.”
—Donald C. Medeiros (20th century)
“Of the two
who feign anger,
sulk in mock sleep,
and give ear
to the other’s halting sighs,
who’s the winner?”
—Hla Stavhana (c. 50 A.D.)
“You are a problem and rune,
you are mystery;
writ on a stone.”
—Hilda Doolittle (1886–1961)