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:
“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)