Comparison with False - something I don't understand

[Nobody]

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.