Turing Oracles
A computer with access to an infinite tape of data is sometimes more powerful than a Turing machine, because the tape can in principle contain the solution to the halting problem, or some other undecidable problem. An infinite tape of data is called a Turing oracle. Even a Turing oracle with random data is not computable (with probability 1), since there are only countably many computations but uncountably many oracles. So a computer with a random Turing oracle can compute things that a Turing machine cannot. A machine which is universal except for having access to some Turing oracle is called weakly universal.
Read more about this topic: Turing Completeness
Famous quotes containing the word oracles:
“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)