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)
“Women, because of their colonial relationship to men, have to fight for their own independence. This fight for our own independence will lead to the growth and development of the revolutionary movement in this country. Only the independent woman can be truly effective in the larger revolutionary struggle.”
—Women’s Liberation Workshop, Students for a Democratic Society, Radical political/social activist organization. “Liberation of Women,” in New Left Notes (July 10, 1967)
“Most childhood problems don’t result from “bad” parenting, but are the inevitable result of the growing that parents and children do together. The point isn’t to head off these problems or find ways around them, but rather to work through them together and in doing so to develop a relationship of mutual trust to rely on when the next problem comes along.”
—Fred Rogers (20th century)
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“Any solution to a problem changes the problem.”
—R.W. (Richard William)