I numeri primi sono una successione?

[Nonno Bassotto]

Beh, andrò un po' OT, ma mi prendo la briga di dare una delle risposte plausibili (dovuta a Kolmogorov) al problema di dire cosa sia un numero casuale. Qualche variante di questa idea permette di definire anche cosa sia una successione casuale di numeri.

In breve definiamo la complessità c(n) di un numero n come il numero di bit necessari a scrivere un programma che dia n come output. Questo dipende dal linguaggio che scegliamo, ma solo a meno di una costante additiva. Diremo che n è casuale se

$ c(n) > [ \log n ] $
dove prendiamo il logaritmo in base 2, cioè il numero di bit necessari a scrivere esplicitamente il numero.

Intuitivamente n è casuale se il più breve programma che dà n come output è

Codice: Seleziona tutto

print n;

Ad esempio $ 2^{100} $ non è casuale perché si fa molto prima a fare un ciclo per moltiplicare per 2 100 volte piuttosto che a scrivere il numero per esteso.

Visto che siamo su un forum di matematica può essere carino dimostrare
1) Per ogni k abbastanza grande esistono numeri casuali di k cifre
e da questo dedurre
2) Per infiniti n vale la stima (ok, è una stima stupida, però l'approccio è carino)
$ \pi(n) \geq \frac{\log n}{\log \log n} $
dove $ \pi(n) $ è il numero di primi fino ad n.

[angus89]

Bè diciamo che l'esempio l'ho capito...anche se non al 100%

non c'è qualcosa non legato all'informatica?
Che ne sò un esempio puramente matematico...

[Nonno Bassotto]

Beh il concetto è fondamentalmente informatico, anche se può essere formalizzato in maniera matematica. Altri esempi

Il numero che esprime la successione del primo miliardo di cifre di pigreco non è casuale: invece che elencare il numero faccio prima a dare un qualsiasi algoritmo per esprimere in successione le cifre di pigreco, ad esempio usando che
$ \pi = 4 \left( 1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots \right) $

n! non è mai casuale, perché posso usare una ricorsione per scriverlo, piuttosto che elencarne le cifre.

Qualsiasi numero primo abbastanza grande non è casuale. Sia infatti p l'n-esimo primo. Allora
$ n \sim \frac{p}{\log p} $
per il teorema dei numeri primi. Per calcolare p mi basta usare un programma che genera la successione dei primi (questo ha lunghezza costante C) e poi mi basta dirgli di fermarsi all'n-esimo primo. In tutto il numero di bit che uso è
$ C + \log \left( \frac{p}{\log p} \right) = C + \log p - \log \log p < \log p $

[angus89]

Vediamo ripartiamo dalla mia richiesta principale...
Esempi di casualità...

Cosa è casuale in matematica?

Io credo che abbiamo una successione casuale se dato l'n-esimo elemento della successione non siamo in grado di prevederne il successivo...
Ma il fatto che non siamo in grado di prevederne il successivo non vuol dire che non esista nessun modo(che non conosciamo) per farlo.
Che ne so dagli esempi che ho letto mi verrebbe da pensare che possa esser casuale l'esito del lancio di un dado...
Anche se si perde la casualità se si pensa deterministicamente...

Oppure dagli esempi mi sembra di capire che una successione casuale possa essere una successione che restituisce per ogni numero, il numero di lettere che lo compone (questo l'ho intuito dagli esempi)
esempi
x(2)=3 (tre lettere)
x(3)=3
x(4)=7
x(5)=6
...
x(n)=?

Daltronde credo che tale successione non possa esser casuale per ovvi motivi...

Tornando in argomento...
Cosa è casuale?
Esempi...

[julio14]

Intuitivamente n è casuale se il più breve programma che dà n come output è

Codice: Seleziona tutto

print n;

anche se non mastichi molta informatica, secondo me ti devi soffermare su questa frase di Nonno Bassotto per comprendere ancora prima di razionalizzare il concetto di casuale.
Proverò a rendere più comprensibile (per come l'ho capita io, perchè se ho capito male sto solo facendo la figura dell'idiota, e non sarebbe una novità) la suddetta frase.

Un oggetto casuale (successione, numero o quant'altro) è qualcosa di non comprensibile dalla nostra ragione se non come se stesso (o a partire da altri oggetti casuali: se prendi un numero casuale e sottrai 1, ottieni ancora un numero casuale). Come diceva NB, la successione delle prime n cifre di $ \pi $ non è casuale perchè la puoi esprimere in un altro modo a partire da oggetti non casuali. E' come se noi partissimo dai numeri naturali, o ancora meglio dall'unità, l'1, e guardassimo tutto quello che ha una qualche connessione con esso: scopriamo così i negativi, i razionali, alcuni tipi di irrazionali come le radici quadre o il pi greco e così via. Tutto ciò che avanza è casuale.

[fph]

Bonus question: esiste o no un programma che calcola il primo numero "casuale" (con la definizione di NB) di n cifre?

[angus89]

Bonus question: esiste o no un programma che calcola il primo numero "casuale" (con la definizione di NB) di n cifre?

Credo di no...

E comunque...
C'è qualcuno in grado di darmi una definizione matemetica di casuale?

[EvaristeG]

beh, quella di nonno bassotto che cos'ha che non va?
sono tutti concetti matematicamente definiti...