Come hai potuto caratterizzare la "vera casualità" di una sequenza finita?

Question

Questa domanda mi è venuta in mente durante la lettura http://arxiv.org/abs/1806.08762/ Qualsiasi sequenza osservata è necessariamente finita e qualsiasi sequenza finita è calcolabile, memorizzando esplicitamente tutti i dati e semplicemente stampandoli, o adattando un polinomiale $ n^{th} $ .

Quindi non esiste una sequenza (finita) (finita), per cui il titolo dell'articolo "sonda sperimentando sperimentalmente l'incomputabilità della casualità quantistica", inizialmente mi ha colpito come un non-sequentur (sebbene i dettagli dell'articolo abbiano un po 'più senso di esso ).

Ma perseguendo il classico senso non sequentro che inizialmente mi è venuto in mente, supponiamo che tu abbia un processo presumibilmente "veramente casuale". Quindi provalo! Nella migliore delle ipotesi, puoi darmi una sequenza finita generata da quel processo. Poi mi adatto a un polinomio, e poof, è pseudo-casuale. Quindi la mia domanda ... quale analisi di una sequenza così finita dimostrerebbe che nel limite $ n a infty $, la tua sequenza pseudo-casuale finita sarebbe veramente casuale (o, in un certo senso di Epsilon-Delta, si avvicina alla vera casualità a qualsiasi precisione desiderata)?

Per la definizione e la semplicità, e per un altro argomento, supponiamo che stiamo parlando di una sequenza di numeri interi casuali da, diciamo, $ 1 $ a $ k $. Poi ci sono sequenze di lunghezza di $ k^n $ n $ e non solo possiamo adattare un polinomio a ciascuno, ma possiamo usare un po 'di enumerazione standard per elenarli tutti. Quindi, la scelta di un numero (casuale o no) $ 1 ldot k^n $ corrisponde alla scelta di un'intera sequenza (casuale o no). Ma i "numeri singoli" non sono in genere considerati casuali in primo luogo, per cui (si potrebbe discutere) nessuno dei due sequenze finite dovrebbe esserlo. Quindi, ancora una volta, come si può dimostrare che il limite $ n a infty $ della sequenza generata da un processo fisico (e presumibilmente casuale) è veramente casuale?

Ciò che mi è venuto in mente come una possibile risposta è che se "veramente_random" $ sim $ non è pubblicabile, quindi considera una sequenza di funzioni calcolabili, dicono i nostri polinomi $ f_n (i), i = 1 ldots n $, tale che $ 1 le f_n (i) le k $ è il numero $ i^{th} $ della sequenza di lunghezza $ n $ generata sperimentalmente. Quindi vorremmo dimostrare che, dato un numero finito di tale calcolabile $ f_n $ 's, la funzione $ lim_ {n a infty} f_n $ non è pubblicabile. Questo può essere fatto (o dimostrabile non fare) e caratterizzerebbe la "vera casualità"?

Modificare
---------
RE @Orlp's Comment, di seguito: sì, immagino di averlo formulato in modo impreciso. In effetti, puoi persino costruire un controesempio più banale alla mia formulazione imprecisa, usando il problema di arresto.

Supponiamo di rivendicare che ha un (diciamo C lingua) funzione INT HALTS (int n) il cui contributo è il numero di Godel di un programma e il cui output è $ 1 $ se un programma n si ferma, o $ 0 $ se no (e diciamo $ -1 $ se n è il numero di Godel di una stringa che non è un programma valido, proprio così Halts () è una funzione totale sul dominio $ mathbb n $). Quindi $ mathbf { mbox {Halts ()}:} mathbb n to {0,1; -1 } $.

E diciamo funzione ausiliaria int godel (char *filename) legge il contenuto del file di testo nome del file, restituendo il suo numero Godel. Ora scrivi il seguente piccolo C programma e mettilo in file doihalt.c

int main ( int argc, char *argv[] ) {
  int halts(), godel();
  while ( halts(godel("doIhalt.c")) == 1 ) ;
  exit ( 0 ); }

Quindi il nostro doihalt Il programma funziona per sempre se Halts () dice che si ferma e in contrario si ferma immediatamente se Halts () dice che funziona per sempre. Quindi, se n = Godel ("Doihalt.C") è il numero di Godel di quel programma, l'unico numero HATTS (N) è immediatamente insolibile. Non hai nemmeno bisogno di una sequenza finita, come nell'esempio di @ORLP, per ottenere un numero non pubblicabile.

Per calcolabilità qui, tuttavia, stiamo parlando di enumerabilità ricorsiva, per cui vengono dati i singoli elementi del nostro insieme di numeri interi e la domanda è se esiste o meno un programma che li elenca tutti. Per i numeri pseudo-casuali generati dal computer, la risposta è una conclusione scontata, "Sì". Ma stiamo chiedendo un processo fisico in scatola nera che in qualche modo genera numerosi numerosi. E dopo un po 'di tempo finito abbiamo accumulato una sequenza di finte della sua produzione. Quindi ovviamente abbiamo nelle nostre mani tutti quei numeri - questa è la premessa per cominciare. E stavo dicendo, o cercando di dire che un insieme finito di numeri che "abbiamo nelle nostre mani" è necessariamente calcolabile (che significa re). Quindi, come lo diresti proprio - e molto più succintamente di quanto l'ho elaborato sopra?

In ogni caso, la mia domanda era allora se il comportamento di quel processo fisico Black-Box è "veramente casuale"-come potremmo rispondere a quella domanda data solo una sequenza finita dell'output della scatola (una stringa di prefisso, per così dire ).

EDIT#2
-------------
RE @DW Commento sotto la sua risposta. Va bene, considerando che il limite $ lim_ {n a infty} F_n $ non è ben definito, la caratterizzazione standard alternativa comporta complessità algoritmica, come segue.

Innanzitutto, per ricapitolare brevemente, abbiamo un processo fisico in scatola nera, generando numeri interi (forse casuali), $ r_i $, uno dopo l'altro, nell'intervallo $ 1 le r_i le k $. E per il primo $ n $ di loro, $ r_1, r_2, ..., r_n $ costruiamo una funzione $ f_n (i) = r_i, i = 1 ... n $. Quindi $ f_ {n+1} $ potrebbe essere necessariamente molto diverso da $ f_n $, o potrebbe essere abbastanza simile.

Si noti che un programma per la funzione $ f_1 più semplice verrebbe solo archiviare $ r_1 $ e stamparlo. Qualsiasi tipo di algoritmo per calcolare che la funzione di dominio a un numero di numerosi sarebbe sicuramente più complicato della semplice stampa. In effetti, lascia $ k (f_n) $ denotare la complessità kolmogorov/algoritmica della funzione (il programma più semplice che calcola) $ f_n $. Quindi i primi $ f_n $ probabilmente sono solo archiviazioni e stampano tutti i corrispondenti $ r_i, i = 1 ... n $.

Ma alla fine, poiché $ n $ diventa abbastanza grande, immagazzinere e stampa presumibilmente non sarebbe il modo più breve/semplice per generare tutti i valori $ n $ necessari $ r_i, i = 1 ... n $. La lunghezza/complessità di un algoritmo sarebbe più breve di tutti i dati necessari. Ma, ovviamente, questo è >> solo se < Esiste un tale algoritmo in primo luogo.

Quindi, per un generatore di numeri pseudo-casuali, sappiamo che c'è un algoritmo. Quindi $ lim_ {n a infty} k (f_n) = const $ perché quello stesso algoritmo calcola tanti numeri casuali che desideri. Altrimenti, per sequenze "veramente casuali", il limite si discosta perché non esiste un algoritmo e alla fine non c'è alternativa all'archiviazione e alla stampa di tutti i dati.

Non sono sicuro se quanto sopra soddisfi tutte le obiezioni di @dw di seguito, ma in ogni caso, data una "stringa prefisso" finita dell'output di Black-Box $ R_i, i = 1 .. .n $, non puoi ancora dire (non credo) se converge o meno quel limite $ k ( CDOT).