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@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---

Reply via email to