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 hpco...@hpcoders.com.au 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.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
