Il 24/09/2020 14:24, pcf ansiagorod ha scritto:
> Ora che mi ci fai pensare non so se possano esistere algoritmi per
> generare numeri realmente casuali; almeno tutti quelli che conosco io
> dall'unico testo in mio possesso che li tratta, non solo sono periodici
> ma la distribuzione non è quasi mai uniforme anche se in alcuni casi
> passano dei test abbastanza severi. Anche se il periodo fosse
> esprimibile con un numero molto grande, probabilmente esisteranno sempre
> applicazioni per cui non è sufficiente.
>
> E a questo punto mi chiedo se esista qualche teorema che garantisca che
> un'algoritmo del genere è possibile anche se non noto.
Sicuramente un algoritmo che giri su un computer reale
senza ricevere infiniti input dall'esterno darà in output,
da un certo punto in poi, una sequenza periodica di bit,
questo perché la memoria di qualsiasi computer è limitata
e a un certo punto il computer si dovrà ritrovare in uno
stato già avuto in precedenza, e quindi ripercorrere
tutti gli stati conseguenti, essendo una macchina
deterministica (automa a stati finiti).
Naturalmente la capacità odierna di memoria dei
computer è tale che anche alla massima velocità
di elaborazione possono eseguire un programma
che darà un output non periodico per tutta la
loro durata di vita (e anche per l'ipotizzabile
"durata di vita" dell'universo ;-).
Ciao
--
Giorgio Bibbiani
(mail non letta)
Received on Thu Sep 24 2020 - 16:03:57 CEST