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