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:
“Tried by a New England eye, or the more practical wisdom of modern times, they are the oracles of a race already in its dotage; but held up to the sky, which is the only impartial and incorruptible ordeal, they are of a piece with its depth and serenity, and I am assured that they will have a place and significance as long as there is a sky to test them by.”
—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.)
“In many ways, life becomes simpler [for young adults]. . . . We are expected to solve only a finite number of problems within a limited range of possible solutions. . . . It’s a mental vacation compared with figuring out who we are, what we believe, what we’re going to do with our talents, how we’re going to solve the social problems of the globe . . .and what the perfect way to raise our children will be.”
—Roger Gould (20th century)