2. Verso una definizione di successione casuale.
Che cosa si intende per successione casuale di numeri? Qual è il concetto intuitivo di casualità che voglio modellizzare matematicamente?
Consideriamo le seguenti stringhe:
α: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
β: yxyxyxyxyxyxyxyxyxyxyxyxyxyxyx
γ: yxxyxxyyxxyxxxxyyyxyxxyxyxxyxy
Intuitivamente diremmo che γ è più "casuale" di β e β è più "casuale" di α.
È facile individuare delle regole di "costruzione" per α e β. E per γ ?
γ è stata generata lanciando una moneta 30 volte (x=testa, y=croce). Tale origine ne garantisce la casualità?
Anche α e β potrebbero essere il frutto del lancio di 30 volte della stessa moneta, e, indicata con S la stringa che codifica le uscite:
Pr(S=α) = Pr(S=β) = Pr(S=γ) = 2–30
L'origine di un evento probabilistico non serve per caratterizzare la casualità di una successione. Cerchiamo un'altra strada.
Supponiamo di dover trasmettere le tre stringhe; possibile soluzione:
(a) scrivi "x" 30 volte
(b) scrivi "yx" 15 volte
(c) scrivi "yxxyxxyyxxyxxxxyyyxyxxyxyxxyxy"
Intuitivamente potremmo dire che una sequenza finita di caratteri è più "casuale" di un'altra sequenza di uguale lunghezza se può essere descritta in un modo più breve di questa.
Che vuol dire "più breve". Per precisare il discorso dobbiamo fissare un linguaggio formale in cui esprimerci.
Che si debba specificare il linguaggio è evidente: se si usasse un "italiano" in cui al posto di "volte", nello stesso significato, si usasse la parola (cioè la sequenza di caratteri) "precipitevolissimevolmente", la descrizione (b) sarebbe più lunga di (c).
Che debba essere "formale" segue dal fatto che le lingue naturali non sono circoscritte in modo netto: sono lingue vive, che evolvono, in cui sorgono nuovi vocaboli, altri vocaboli spariscono, e in cui i significati dei vocaboli possono cambiare nel tempo (oltre a presentare elementi di ambiguità, per cui non è detto che a una frase si riesca a dare, senza altre informazioni, univocamente un significato).
Ad esempio usiamo il QBasic, in una versione ristretta, limitandolo a lavorare su numeri-macchina naturali (supponiamo senza limiti superiori) e ammettendo come sole funzioni numeriche "+" e "–".
I tre procedimenti possono essere descritti con:
FOR i=1 TO 30:PRINT "x";:NEXT
FOR i=1 TO 15:PRINT "yx";:NEXT
PRINT "yxxyxxyyxxyxxxxyyyxyxxyxyxxyxy"
La registrazione del primo testo (che può essere scritto con un qualunque editor) occupa 29·8 bit = 232 bit (in codice ascii ogni carattere è rappresentato da una sequenza di 8 bit, cioè 1 byte: vedi Gli Oggetti Matematici).
Il secondo testo occupa 30·8 bit = 240 bit.
Il terzo occupa 38·8 bit = 304 bit
Fissato il nostro linguaggio, abbiamo che la stringa γ non può essere generata con un programma più breve di quello indicato, che ne elenca tutti i caratteri (la cosa può essere dimostrata facilmente: i programmi lunghi meno di 304 bit sono in quantità finita). Le altre due stringhe possono essere descritte con programmi che occupano meno di 304 bit.
È evidente che questa "definizione" di "più casuale di" dipende dal linguaggio scelto per descrivere gli algoritmi e dal modo in cui lo abbiamo codificato.
Ad esempio con il nostro linguaggio le stringhe di 17 caratteri "11111111111111111" e "17696078910318549" hanno lo stesso livello di casualità: FOR I=1 TO 17:PRINT "1";:NEXT è costituito da 29 caratteri, non è più breve di PRINT "11111111111111111".
Ma se il linguaggio contenesse anche un'istruzione LOOP tale che LOOP n:…:NEXT (se in "…" non compare "i") sia equivalente a FOR i=1 TO n:…:NEXT, potremmo descrivere la prima stringa con il programma LOOP 17:PRINT "1";:NEXT che è costituito solo da 25 caratteri. In questo caso la prima stringa sarebbe meno casuale della seconda.
Diversi potrebbero risultare i confronti di casualità se ad esempio si codificasse ogni parola chiave (print, for, …) con 1 solo byte (tra i 256 byte 00000000, 00000001, …, 11111111 utilizzati dal codice ascii soli i primi 128 byte 00000000, 00000001, …, 01111111 rappresentano caratteri standard, per cui potremmo impiegare qualcuno degli altri byte, inizianti con "1", per codificare le parole chiave).
Ad esempio il programma FOR I=1 TO 17:PRINT "1";:NEXT diventerebbe di 19 byte, più breve di PRINT "11111111111111111", che sarebbe di 21 byte.
Nota. In genere si codificano (sul concetto di codice ritorneremo successivamente) i messaggi (per confrontarne la "lunghezza") in forma binaria, cioè usando l'alfabeto {0,1}, in quanto questa è la modalità di registrazione (attraverso elementi bistabili) impiegata nei mezzi di calcolo elettronici. I confronti non cambierebbero sostanzialmente se si utilizzasse ad esempio un alfabeto di 3 caratteri, come {0,1,2}. Chiamando ter uno di questi caratteri, potremmo impiegare gruppi di 5 ter, da 00000 a 11111, per rappresentare 3^5=243 caratteri. Due messaggi che sono uno più lungo dell'altro con la codifica in bit sono uno più lungo dell'altro, o al più lunghi uguali, anche con la codifica in ter; e viceversa.
Vedremo, poi, come questo discorso può essere esteso alle successioni infinite: questo è l'aspetto che ci interessa relativamente alla questione di definire la casualità. E in questo caso la scelta del linguaggio sarà ininfluente.
| <<< Paragrafo precedente | Paragrafo successivo >>> |