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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Mon Aug 28 2006 - 09:27:08 PDT