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)
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—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.)
“A serious problem in America is the gap between academe and the mass media, which is our culture. Professors of humanities, with all their leftist fantasies, have little direct knowledge of American life and no impact whatever on public policy.”
—Camille Paglia (b. 1947)