Vorrei sapere come si definiscono i numeri casuali in informatica. Vi sono varie definizioni? E che legame c’è tra numeri casuali e teorema di Gödel? Grazie e complimenti per questo sito stupendo.

La generazione di numeri casuali è tra le classi di problemi cosiddetti “notevoli”, nella teoria dei numeri: ottenere infatti una sequenza di numeri
casuali è di cruciale importanza nelle simulazioni di comportamento di
sistemi regolati da variabili aleatorie.

Verso la fine degli anni `20 sono state stilate diverse tavole di numeri
casuali, ma bisogna attendere la fine della seconda guerra mondiale per
avere il primo tentativo di approccio algoritmico, dovuto a John Von Neumann,
importantissima figura di scienziato a cui oggi dobbiamo un considerevole
numero di lavori, tra cui la teoria dei giochi, la formalizzazione
matematica dei processi di meccanica quantistica¸ la partecipazione
al Progetto Manhattan, diversi ed importantissimi risultati sulla
teoria della commutabilità.

L`algoritmo di Von Neumann, detto middle-square è estremamente
semplice: si prende un valore iniziale, detto seme dell`algoritmo
di generazione, lo si eleva al quadrato e si estrae la porzione centrale
del numero così ottenuto.

Ad esempio, per generare una serie di numeri casuali a due cifre, partendo
dal seme 64, si ottiene:

642=4096, da cui si estrae la parte centrale (con ugual numero di
cifre del seme), per cui il prossimo numero casuale è 9, il processo si
ripete ottenendo la serie: 81, 56, 13, 6, 36 ….

Algoritmi di questo tipo vengono detti Generatori di numeri pseudocasuali.

Si dimostra che la successione pseudocasuale così ottenuta, dopo un
certo numero di iterazioni, si ripete. La bontà di algoritmi di questo
tipo sta proprio nel periodo di ricorrenza dei numeri casuali così
ottenuti. Maggiore è il periodo, migliore è l`algoritmo utilizzato.

Esistono tuttavia dei valori di seme per cui il periodo di ricorrenza
è minimo, come ad esempio il valore 0, che restituisce tutti 0 usando il
metodo middle-square.

Un buon generatore pseudo-casuale è il cosiddetto Generatore Lineare
Congruente
, sempre di tipo iterativo, che si basa su due semi a
e b ed un modulo m.

L`equazione alle ricorrenze che descrive il GLC è:

Xn+1=(aXn+b) mod m

L`espressione mod m sta ad indicare che il generatore
restituisce valori interi compresi tra 0 ed m.

Ad esempio, per a=18, b=22, m=99 il GLC restituisce la sequenza:

iteraz. Valore
1 40
2 49
3 13
4 58
5 76
6 4
7 94
8 31
9 85
10 67
11 40
12 49
13 13
14 58
15 76
16 4
17 94
18 31
19 85

Come si osserva, con questi valori specifici di seme, il generatore
ripete la sequenza solamente ogni dieci iterazioni.

Si dimostra che un metodo efficace di scelta dei valori di seme è di
utilizzare potenze di 2 anche se questo accorgimento non mette al riparo
dal fenomeno del ripetersi dei numeri casuali.

Uno dei principali risultati di Gödel è stato il dimostrare che il
numero di programmi scrivibili è enumerabile, ovvero è di ordine
di infinito pari all`insieme degli interi. Da qui ciò prova l`attuablità
del cosiddetto processo di Gödelizzazione, ovvero di assegnazione
di un numero intero che rappresenti univocamente il programma scritto,
ovvero: per ogni programma di computer (in qualsiasi linguaggio) esiste
un numero naturale intero n che vi corrisponde. Tale rappresentazione
è talmente univoca, che n può essere associato alla semantica
del programma scritto (ovvero ne può descrivere completamente il significato).

Si immagini di avere un programma di computer avente:

  • n: il numero di Gödel del programma
  • x: il valore ottenuto in output dal programma
  • y1,…,ym: variabili di programma

e si costruisca un polinomio P(n, x, y1,…,ym),
in modo che questi valga 0 se e solo se il programma di semantica n
restituisce il valore x usando le variabili y1,…,ym.

Ci si ponga adesso la questione: è possibile ottenere il numero di
Gödel di un programma come risultato del programma stesso? Ovvero, cosa
accade quando x=n ?

Si dimostra, che non esiste alcun algoritmo e quindi programma di
computer, che decida se l`equazione P(n, n, y1,…,ym)=0
ha una soluzione. Questo fatto è una rappresentazione alternativa del teorema
di Godel: dire che non esiste alcun algoritmo che computi la decidibilità
dell`equazione implica che non esiste alcun sistema assiomatico per determinare
la stessa cosa.

Si badi bene: non esiste un algoritmo in grado di determinare se l`equazione
è risolvibile per n qualsiasi. Al variare di n, quindi, il
fatto che l`equazione ha una soluzione o meno è, quindi completamente casuale
e richiede la scrittura di un programma specifico per determinare se l`equazione
ha una soluzione (abbiamo visto che non ne esiste, infatti, uno generico).

Si supponga quindi che tali programmi restituiscano 0 o uno a seconda
della risolvibilità dell`equazione P(n, n, y1,…,ym)=0:
la sequenza di 0 e 1 è completamente casuale, ovvero sono caratterizzati
da una variabile aleatoria analoga a quella che caratterizza il lancio
di una moneta.