Posted by
Russell Standish-2 on
Apr 28, 2019; 12:26am
URL: http://friam.383.s1.nabble.com/A-question-for-tomorrow-tp7593073p7593109.html
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
[hidden email]
Economics, Kingston University
http://www.hpcoders.com.au----------------------------------------------------------------------------
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
to unsubscribe
http://redfish.com/mailman/listinfo/friam_redfish.comarchives back to 2003:
http://friam.471366.n2.nabble.com/FRIAM-COMIC
http://friam-comic.blogspot.com/ by Dr. Strangelove