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)
“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.)
“Nothing in the world can take the place of Persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and Determination alone are omnipotent. The slogan “Press On”, has solved and will always solve the problems of the human race.”
—Calvin Coolidge (1872–1933)