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)
“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.)
“Sustained unemployment not only denies parents the opportunity to meet the food, clothing, and shelter needs of their children but also denies them the sense of adequacy, belonging, and worth which being able to do so provides. This increases the likelihood of family problems and decreases the chances of many children to be adequately prepared for school.”
—James P. Comer (20th century)