On Mon, 06 Dec 2010 08:32:18 -0500, Mel wrote: > Apparently, at the end of his research, Alan Turing was trying out the idea > of 'oracles', where a computable process would have access to an > uncomputable process to get particular results. I would imagine that the > idea here was to clarify what this would do to the computable process. If > he had lived, I doubt that Turing would have built an oracle, but the idea > does live on in interactive debuggers.
The "oracle" concept was introduced quite early on in Turing's work, late 1930s. The idea is to examine the complexity of problems relative to other problems. E.g. if you have a Turing machine with access to an oracle which can solve some NP-complete problem, you can analyse the complexity of solving other NP-complete problems in that context. -- http://mail.python.org/mailman/listinfo/python-list