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)
“People seldom see the halting and painful steps by which the most insignificant success is achieved.”
—Anne Sullivan (1866–1936)
“I have a horror of people who speak about the beautiful. What is the beautiful? One must speak of problems in painting!”
—Pablo Picasso (1881–1973)