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:
“In excited conversation we have glimpses of the universe, hints of power native to the soul, far-darting lights and shadows of an Andes landscape, such as we can hardly attain in lone meditation. Here are oracles sometimes profusely given, to which the memory goes back in barren hours.”
—Ralph Waldo Emerson (1803–1882)
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“The truth of the thoughts that are here set forth seems to me unassailable and definitive. I therefore believe myself to have found, on all essential points, the final solution of the problems. And if I am not mistaken in this belief, then the second thing in which the value of this work consists is that it shows how little is achieved when these problems are solved.”
—Ludwig Wittgenstein (1889–1951)