La generazione di numeri casuali \u00e8 tra le classi di problemi cosiddetti “notevoli”, nella teoria dei numeri: ottenere infatti una sequenza di numeri
\ncasuali \u00e8 di cruciale importanza nelle simulazioni di comportamento di
\nsistemi regolati da variabili aleatorie. <\/p>\n
Verso la fine degli anni `20 sono state stilate diverse tavole di numeri
\ncasuali, ma bisogna attendere la fine della seconda guerra mondiale per
\navere il primo tentativo di approccio algoritmico, dovuto a John Von Neumann,
\nimportantissima figura di scienziato a cui oggi dobbiamo un considerevole
\nnumero di lavori, tra cui la teoria dei giochi<\/i>, la formalizzazione
\nmatematica dei processi di meccanica quantistica<\/i>\u00b8 la partecipazione
\nal Progetto Manhattan<\/i>, diversi ed importantissimi risultati sulla
\nteoria della commutabilit\u00e0<\/i>.<\/p>\n
L`algoritmo di Von Neumann, detto middle-square<\/i> \u00e8 estremamente
\nsemplice: si prende un valore iniziale, detto seme<\/i> dell`algoritmo
\ndi generazione, lo si eleva al quadrato e si estrae la porzione centrale
\ndel numero cos\u00ec ottenuto.<\/p>\n
Ad esempio, per generare una serie di numeri casuali a due cifre, partendo
\ndal seme 64, si ottiene:<\/p>\n
642<\/sup>=4096, da cui si estrae la parte centrale (con ugual numero di Algoritmi di questo tipo vengono detti Generatori di numeri pseudocasuali<\/i>.<\/p>\n Si dimostra che la successione pseudocasuale cos\u00ec ottenuta, dopo un Esistono tuttavia dei valori di seme per cui il periodo di ricorrenza Un buon generatore pseudo-casuale \u00e8 il cosiddetto Generatore Lineare L`equazione alle ricorrenze che descrive il GLC \u00e8: L`espressione mod<\/i> m<\/i> sta ad indicare che il generatore Ad esempio, per a=18, b=22, m=99<\/i> il GLC restituisce la sequenza: <\/p>\n Come si osserva, con questi valori specifici di seme, il generatore Si dimostra che un metodo efficace di scelta dei valori di seme \u00e8 di Uno dei principali risultati di G\u00f6del \u00e8 stato il dimostrare che il Si immagini di avere un programma di computer avente:<\/p>\n e si costruisca un polinomio P(n, x, y1<\/sub>,\u2026,ym<\/sub>)<\/i>, Ci si ponga adesso la questione: \u00e8 possibile ottenere il numero di Si dimostra, che non esiste alcun algoritmo e quindi programma di Si badi bene: non esiste un algoritmo in grado di determinare se l`equazione Si supponga quindi che tali programmi restituiscano 0 o uno a seconda <\/p>\n","protected":false},"excerpt":{"rendered":" […]<\/p>\n","protected":false},"author":180,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[60],"tags":[],"class_list":["post-1463","post","type-post","status-publish","format-standard","hentry","category-domande-varie-informatica-e-telecomunicazioni"],"_links":{"self":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/1463","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/users\/180"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/comments?post=1463"}],"version-history":[{"count":0,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/posts\/1463\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/media?parent=1463"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/categories?post=1463"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vialattea.net\/content\/wp-json\/wp\/v2\/tags?post=1463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\ncifre del seme), per cui il prossimo numero casuale \u00e8 9, il processo si
\nripete ottenendo la serie: 81, 56, 13, 6, 36 \u2026.<\/p>\n
\ncerto numero di iterazioni, si ripete. La bont\u00e0 di algoritmi di questo
\ntipo sta proprio nel periodo di ricorrenza<\/i> dei numeri casuali cos\u00ec
\nottenuti. Maggiore \u00e8 il periodo, migliore \u00e8 l`algoritmo utilizzato.<\/p>\n
\n\u00e8 minimo, come ad esempio il valore 0, che restituisce tutti 0 usando il
\nmetodo middle-square<\/i>.<\/p>\n
\nCongruente<\/i>, sempre di tipo iterativo, che si basa su due semi a<\/i>
\ne b<\/i> ed un modulo m<\/i>.<\/p>\n
<\/p>\n
\nrestituisce valori interi compresi tra 0<\/i> ed m<\/i>.<\/p>\n
<\/p>\n\n\n
\n iteraz.<\/td>\n Valore <\/td>\n<\/tr>\n \n 1 <\/td>\n 40 <\/td>\n<\/tr>\n \n 2 <\/td>\n 49 <\/td>\n<\/tr>\n \n 3 <\/td>\n 13 <\/td>\n<\/tr>\n \n 4 <\/td>\n 58 <\/td>\n<\/tr>\n \n 5 <\/td>\n 76 <\/td>\n<\/tr>\n \n 6 <\/td>\n 4 <\/td>\n<\/tr>\n \n 7 <\/td>\n 94 <\/td>\n<\/tr>\n \n 8 <\/td>\n 31 <\/td>\n<\/tr>\n \n 9 <\/td>\n 85 <\/td>\n<\/tr>\n \n 10 <\/td>\n 67 <\/td>\n<\/tr>\n \n 11 <\/td>\n 40 <\/td>\n<\/tr>\n \n 12 <\/td>\n 49 <\/td>\n<\/tr>\n \n 13 <\/td>\n 13 <\/td>\n<\/tr>\n \n 14 <\/td>\n 58 <\/td>\n<\/tr>\n \n 15 <\/td>\n 76 <\/td>\n<\/tr>\n \n 16 <\/td>\n 4 <\/td>\n<\/tr>\n \n 17 <\/td>\n 94 <\/td>\n<\/tr>\n \n 18 <\/td>\n 31 <\/td>\n<\/tr>\n \n 19 <\/td>\n 85 <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
\nripete la sequenza solamente ogni dieci iterazioni.<\/p>\n
\nutilizzare potenze di 2 anche se questo accorgimento non mette al riparo
\ndal fenomeno del ripetersi dei numeri casuali. <\/p>\n<\/p>\n
\nnumero di programmi scrivibili \u00e8 enumerabile<\/i>, ovvero \u00e8 di ordine
\ndi infinito pari all`insieme degli interi. Da qui ci\u00f2 prova l`attuablit\u00e0
\ndel cosiddetto processo di G\u00f6delizzazione,<\/i> ovvero di assegnazione
\ndi un numero intero che rappresenti univocamente il programma scritto,
\novvero: per ogni programma di computer (in qualsiasi linguaggio) esiste
\nun numero naturale intero n<\/i> che vi corrisponde. Tale rappresentazione
\n\u00e8 talmente univoca, che n<\/i> pu\u00f2 essere associato alla semantica
\n<\/i>del programma scritto (ovvero ne pu\u00f2 descrivere completamente il significato).<\/p>\n\n
\nin modo che questi valga 0 se e solo se il programma di semantica n<\/i>
\nrestituisce il valore x<\/i> usando le variabili y1<\/sub>,\u2026,ym<\/sub>.<\/i><\/p>\n
\nG\u00f6del di un programma come risultato del programma stesso? Ovvero, cosa
\naccade quando x=n<\/i> ?<\/p>\n
\ncomputer, che decida se l`equazione P(n, n, y1<\/sub>,\u2026,ym<\/sub>)=0<\/i>
\nha una soluzione. Questo fatto \u00e8 una rappresentazione alternativa del teorema
\ndi Godel: dire che non esiste alcun algoritmo che computi la decidibilit\u00e0
\ndell`equazione implica che non esiste alcun sistema assiomatico per determinare
\nla stessa cosa.<\/p>\n
\n\u00e8 risolvibile per n qualsiasi<\/i>. Al variare di n<\/i>, quindi, il
\nfatto che l`equazione ha una soluzione o meno \u00e8, quindi completamente casuale
\ne richiede la scrittura di un programma specifico per determinare se l`equazione
\nha una soluzione (abbiamo visto che non ne esiste, infatti, uno generico).<\/p>\n
\ndella risolvibilit\u00e0 dell`equazione P(n, n, y1<\/sub>,\u2026,ym<\/sub>)=0<\/i>:
\nla sequenza di 0 e 1 \u00e8 completamente casuale, ovvero sono caratterizzati
\nda una variabile aleatoria analoga a quella che caratterizza il lancio
\ndi una moneta.<\/p>\n
<\/p>\n