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)
“It is not impossible, of course, after such an administration as Roosevelt’s and after the change in method that I could not but adapt in view of my different way of looking at things, that questions should arise as to whether I should go back on the principles of the Roosevelt administration.... I have a government of limited power under a Constitution, and we have got to work out our problems on the basis of law. Now, if that is reactionary, then I am a reactionary.”
—William Howard Taft (1857–1930)