On Wed, May 21, 2014 at 06:22:13PM +0200, Bruno Marchal wrote: > > It has been shown, by Kurtz(*), that some problem in arithmetic can > be solved by a machine using a random oracle only, and thus by no > machine using any pseudo-random subroutine. > > Note that if comp is true, then self-multiplication makes office of > random oracle in the FPI on the sigma_1 complete set, or UD*, so > comp predicts locally some random oracle, as quantum physics suggest > too (with or without the MW). I guess it is part of the arithmetical > phasing out of the white rabbits. > > Bruno > > (*) KURTZ S. A., 1983, On the Random Oracle Hypothesis, Information > and Control, 57, pp. > 40-47. > >
Are you sure that's right? I thought that some NP hard problems become tractable with a random oracle, not that some noncomputable problems become computable. I raise you: Chang et al., (1994) "The Random Oracle Hypothesis is False", J. Computer and Systems Science, 49, pp24-39 and Leeuw et al., (1956) "Computation by probabilistic machines", in Automata Studies, Shannon (ed), (Princeton UP). pp183-212. -- ---------------------------------------------------------------------------- Prof Russell Standish Phone 0425 253119 (mobile) Principal, High Performance Coders Visiting Professor of Mathematics [email protected] University of New South Wales http://www.hpcoders.com.au Latest project: The Amoeba's Secret (http://www.hpcoders.com.au/AmoebasSecret.html) ---------------------------------------------------------------------------- -- 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 [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
