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:
“These marbles, the works of the dreamers and idealists of old, live on, leading and pointing to good. They are the works of visionaries and dreamers, but they are realizations of soul, the representations of the ideal. They are grand, beautiful, and true, and they speak with a voice that echoes through the ages. Governments have changed; empires have fallen; nations have passed away; but these mute marbles remain—the oracles of time, the perfection of art.”
—Herman Melville (1819–1891)
“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.)
“To be a philosopher is not merely to have subtle thoughts, nor even to found a school, but so to love wisdom as to live according to its dictates a life of simplicity, independence, magnanimity, and trust. It is to solve some of the problems of life, not only theoretically, but practically.”
—Henry David Thoreau (1817–1862)