Le 28-août-06, à 05:37, Stathis Papaioannou a écrit :
>> It *has* been proved (by diagonalization) that there exist some >> problem >> in number theory which are soluble by a machine using a random oracle, >> although no machine with pseudorandom oracle can sole the problem. > > That's interesting: does this imply it is possible to test a number > sequence to see > if it is random? Alas No. That would contradict other theorems in computer science. So we can infer that Kurtz diagonalization is non constructive. I will check Kurtz's paper to verify. > >> KURTZ S. A., 1983, On the Random Oracle Hypothesis, Information and >> Control, 57, pp. 40-47. >> >> But it is not relevant given that self-duplication is already a way to >> emulate true random oracle. > > Do you mean by this an algorithm that explores every possible branch, > by analogy > with the MWI of QM? Yes. Just think about the UD. It generates all the possible computational branches (if you accept CT, and AR. No need for YD here). Bruno http://iridia.ulb.ac.be/~marchal/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---
