Il codice che termina in una condizione casuale è garantito per terminare?

Per definizione, deve essere possibile ottenere una sequenza infinita di 0 in una sequenza davvero casuale ("casuale"), quindi questo programma deve essere in grado di funzionare per sempre. Altrimenti, questo non può essere considerato una sequenza casuale dal punto di vista matematico / statistico. Non puoi escludere una sequenza specifica e legittima e considera il tuo sistema davvero casuale.

Una sequenza infinita di 0 non sarebbe riconosciuta come una sequenza casuale legittima dalla maggior parte se non tutti i metodi statistici standard di analisi che usiamo in pratica ma, nonostante ciò, in realtà è una sequenza casuale perfettamente legittima per la teoria.

Questo in teoria.

In pratica, sappiamo tutti che, dato un tempo sufficiente, otterremo un numero diverso da 0 e il programma terminerà.

Il generatore casuale usato dai computer è considerato casuale quando una sequenza di numeri ragionevolmente lunga che generano (per esempio, qualche milione di numeri ...) non può essere distinta da una veramente casuale quando analizzata con strumenti statistici standard. Cioè: non sappiamo davvero se la sequenza di numeri che generano è davvero casuale, ma non possiamo distinguerla da una vera sequenza casuale quando analizziamo un campione di lunghezza finita.

Questa è una grande differenza perché ... data una sequenza più lunga puoi scoprire che la tua sequenza non è realmente casuale e può essere riprodotta. In crittografia, questa sarebbe una pessima scoperta.

Come ho detto sopra, i metodi statistici di analisi che usiamo non riconoscono una sequenza infinita di 0 come una sequenza casuale legittima. Tuttavia, questo è un fallimento dei metodi analitici, non del generatore casuale. Matematicamente parlando, non puoi escludere una tale sequenza solo perché non soddisfa il tuo sistema analitico o il tuo gusto personale. Se non hai una vera ragione matematica per escluderlo, è legittimo.

Sì, dato tempo infinito il codice terminerebbe sicuramente. Vedi teorema infinito di scimmia . La probabilità che funzioni per sempre è 0, c'è una prova matematica per questo.
Questo è se i numeri erano veramente casuali. Non ne so abbastanza dei generatori di numeri casuali per dirti di più.

Per rispondere all'altra parte della tua domanda (riguardante l'implementazione di random ), direi che dipende interamente dall'implementazione. Dividere le implementazioni in generatori di numeri pseudo-casuali e generatori di numeri casuali "veri".

Una popolare implementazione di un generatore di numeri pseudo-casuali è un registro a scorrimento lineare di feedback ( LFSR ). Questi in realtà generano sequenze ripetibili di numeri e sono solo casuali nel senso di soddisfare una distribuzione casuale. Esiste, infatti, un'entità chiamata "lunghezza massima LFSR" che è garantita per scorrere tutti i valori. In tal caso, il tuo codice terminerà sicuramente.

I "veri" generatori di numeri casuali non possono essere implementati solo nel software. Hanno bisogno di una sorta di sorgente di "rumore" fondamentale: tipicamente una giunzione PN polarizzata inversa con un amplificatore, o una stazione radio sintonizzata su una scheda audio, dove si campiona il bit più piccolo. A volte c'è una sorgente incorporata nel sistema operativo che tenta di generare bit casuali usando entropia come tempi di I / O del disco, tempi della tastiera, ecc. In tal caso, si sta parlando di un vero e proprio processo fisico casuale (quantico) mai generare uno zero, e per quello forse abbiamo bisogno di consultare un fisico.

Comprendi anche che persino un'implementazione veramente casuale può non essere veramente casuale se c'è un difetto sottile che non genera mai un sottoinsieme di numeri.

Penso che il codice tutto sia garantito per terminare, poiché alla fine l'entropia eliminerà tutti i differenziali energetici, rendendo impossibile per i circuiti logici cambiare stato. Tuttavia, uno degli attributi di un generatore di numeri veramente casuale è che potrebbe mai produrre un numero particolare, così come può produrre tirature infinitamente lunghe di un particolare numero. Quindi la risposta alla tua domanda è "sì, ma non perché soddisfi il tuo criterio di uscita".