[FRIAM] A question for tomorrow

[Russell Standish]

On Sat, Apr 27, 2019 at 11:28:41AM -0600, Frank Wimberly wrote:
> 
> Lee, Surely someone has developed probabilistic Turing Machines which can, very
> rarely, make errors.  I am ignorant of the field since 1972 when I took a
> course which used Hopcroft and Ullman as a text.
> 
> Nick, I agree that your questions are charming.  Your humanity is clearly
> seen.  By the way, it occurred to me this morning that the motto of
> behaviorists should be, "If it talks like a duck🦆...etc"
> 
> Frank
> 

There is a small amount of literature on probabilistic Turing
machines, which tends to go under the name "Turing machine with random
oracle".

The first result was an early one of Shannon's, who showed that adding
a random oracle did not increase the set of functions that are
computable.

However, conversely, there appear to interesting results that indicate
P=NP for random oracle machines. There is some controversy over this,
though, and personally, I've never been able to follow the proofs in
the area :).

If true, it meshes in well with the idea that evolutionary algorithms
exploit the obvious random oracles of "Variation" to effectively solve
some very NP hard problems.


-- 

----------------------------------------------------------------------------
Dr Russell Standish                    Phone 0425 253119 (mobile)
Principal, High Performance Coders
Visiting Senior Research Fellow        hpcoder at hpcoders.com.au
Economics, Kingston University         http://www.hpcoders.com.au
----------------------------------------------------------------------------