On 12 Jun 2017, at 01:46, Russell Standish wrote:
On Sun, Jun 11, 2017 at 10:34:44AM +0200, Bruno Marchal wrote:
KURTZ S. A., 1983, On the Random Oracle Hypothesis, Information and
Control, 57, pp. 40-47.
And I raise you with
@Article{Chang-etal94,
author = {Richard Chang and Benny Chor and Oded Goldreich and
Juris Hartmanis and Johan H\aa{}stad and Desh Ranjan and Pankaj
Rohatgi},
title = {The Random Oracle Hypothesis is False},
journal = {Journal of Computer and System Sciences},
year = 1994,
volume = 49,
pages = {24-39}
}
I am still searching my Kurtz paper. Hartmanis is usually good, but my
memory of this is that this paper shows only that the random
hypothesis is false *FAPP*. It makes Kurtz result less interesting,
but still relevant for the FPI and physics extraction (as the UD
contains by construction a random oracle, and all oracles, but only
the random one has a clear role, and a promising one finding some
equivalent in arithmetic for a phase randomization similar to Feynman.
Note that if Riemann hypothesis is true, we should be able to extract
a random oracle from the distribution of prime. The same would occur
if we could prove that the decimal sequence of some constructive
(transcendental) number is random.
Seriously, there is an easy proof that probabilistic Turing machines
are incapable of implementing any algorithm a Turing machine can't:
@InCollection{Leeuw-etal56,
author = {Karel de Leeuw and Edward F. Moore and Claude E.
Shannon and N. Shapiro},
title = {Computation by Probabilistic Machines},
booktitle = {Automata Studies},
pages = {183--212},
publisher = {Princeton UP},
year = 1956,
editor = {Shannon and McCarthy},
address = {Princeton}
}
This is well known. The point I made was not on "computation", but on
the ability of proving or solving some problem. Probabilistic and
quantum machines do not violate the Church-Turing thesis, and all
known universal formalism compute the same functions than a combinator
or Turing machine, but of course such combinators or Turing machine
can prove or believe quite different set of (arithmetical)
propositions, and solve different class of problems.
Bruno
However, it appears that NP-complete problems become P when a random
oracle is added to the mix, so there is a difference from a
computational complexity point of view. I confess to not understanding
that proof, but it is in Chang et al op. cit.
Cheers
--
----------------------------------------------------------------------------
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
----------------------------------------------------------------------------
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
