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 to, relationship, halting and/or problem:
“Whatever may be our just grievances in the southern states, it is fitting that we acknowledge that, considering their poverty and past relationship to the Negro race, they have done remarkably well for the cause of education among us. That the whole South should commit itself to the principle that the colored people have a right to be educated is an immense acquisition to the cause of popular education.”
—Fannie Barrier Williams (1855–1944)
“Sometimes in our relationship to another human being the proper balance of friendship is restored when we put a few grains of impropriety onto our own side of the scale.”
—Friedrich Nietzsche (1844–1900)
“Poetry is above all a concentration of the power of language, which is the power of our ultimate relationship to everything in the universe.”
—Adrienne Rich (b. 1929)
“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.)
“It is part of the educator’s responsibility to see equally to two things: First, that the problem grows out of the conditions of the experience being had in the present, and that it is within the range of the capacity of students; and, secondly, that it is such that it arouses in the learner an active quest for information and for production of new ideas. The new facts and new ideas thus obtained become the ground for further experiences in which new problems are presented.”
—John Dewey (1859–1952)