Oracles and Halting Problems
It is possible to posit the existence of an oracle which computes a non-computable function, such as the answer to the halting problem or some equivalent. A machine with an oracle of this sort is a hypercomputer.
Interestingly, the halting paradox still applies to such machines; although they determine whether particular Turing machines will halt on particular inputs, they cannot determine, in general, if machines equivalent to themselves will halt. This fact creates a hierarchy of machines, called the arithmetical hierarchy, each with a more powerful halting oracle and an even harder halting problem.
Read more about this topic: Oracle Machine
Famous quotes containing the words oracles, halting and/or problems:
“For what are the classics but the noblest thoughts of man? They are the only oracles which are not decayed, and there are such answers to the most modern inquiry in them as Delphi and Dodona never gave. We might as well omit to study Nature because she is old.”
—Henry David Thoreau (1817–1862)
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“If family communication is good, parents can pick up the signs of stress in children and talk about it before it results in some crisis. If family communication is bad, not only will parents be insensitive to potential crises, but the poor communication will contribute to problems in the family.”
—Donald C. Medeiros (20th century)