Comment pourriez-vous caractériser la «vraie aléatoire» d'une séquence finie?

Question

Cette question m'est venue à l'esprit pendant la lecture http://arxiv.org/abs/1806.08762/ Toute séquence observée est nécessairement finie, et toute séquence finie est calculable, soit en stockant explicitement toutes les données et en les imprimant simplement, soit en ajustant un polynôme $ n ^ {th} $ - de degré à une séquence de longueur $ n $, etc. .

Il n'y a donc pas une séquence non ordinable (finie), par laquelle le titre de l'article "sonder expérimentalement l'incomputabilité de l'aléatoire quantique", m'a initialement frappé comme un peu non séquenti ).

Mais en poursuivant le sens du non-séquentiment classique qui m'est initialement venu à l'esprit, supposons que vous ayez un processus prétendu être "vraiment aléatoire". Alors prouvez-le! Au mieux, vous pouvez me donner une séquence finie générée par ce processus. Ensuite, je m'adapte juste un polynôme, et Poof, c'est pseudo-aléatoire. Donc ma question ... quelle analyse d'une telle séquence finie prouverait que dans la limite $ n to infty $, votre séquence pseudo-aléatoire finie serait vraiment aléatoire (ou, dans un sens d'Epsilon-Delta, approche de la véritable aléatoire. à toute précision souhaitée)?

Pour la définition et la simplicité, et pour un autre argument, supposons que nous parlons d'une séquence d'entiers aléatoires de, disons, 1 $ à $ k $. Ensuite, il y a des séquences de $ k ^ n $ $ n $, et non seulement nous pouvons adapter un polynôme à chacun, nous pouvons utiliser un énumération standard pour les énumérer tous. Ensuite, le choix d'un seul numéro (aléatoire ou non) 1 ldots k ^ n $ correspond à choisir une séquence entière (aléatoire ou non). Mais les «nombres uniques» ne sont généralement pas considérés comme aléatoires en premier lieu, par lequel (on pourrait affirmer) non plus les séquences finies ne devraient être. Alors, encore une fois, comment pourriez-vous prouver que la limite $ n à infty $ de la séquence générée par un processus physique (et soi-disant aléatoire) est vraiment aléatoire?

Ce qui m'est venu à l'esprit comme une réponse possible, c'est que si "véritablement_random" $ sim $ non ordinable, alors envisagez une séquence de fonctions calculables, dites nos polynômes $ f_n (i), i = 1 ldots n $, tel que 1 le le f_n (i) le k $ est le nombre $ i ^ {th} $ de la séquence $ n $-LONGNE générée expérimentalement. Ensuite, nous voudrions prouver que, compte tenu d'un nombre fini de tels $ F_N $, la fonction $ lim_ {n à infty} f_n $ est non computable. Cela peut-il être fait (ou ne fait pas de fait), et cela caractériserait-il le «vrai aléatoire»?

Éditer
---------
Le commentaire de RE @ ORLP, ci-dessous: Oui, je suppose que je l'ai formulé de manière imprécis. En effet, vous pouvez même construire un contre-exemple plus trivial à mon libellé imprécis, en utilisant le problème d'arrêt.

Supposons que vous prétendez avoir un (disons C fonction du language int halts (int n) dont la contribution est le numéro Godel d'un programme, et dont la production est un $ de $ si le programme n Horte, ou 0 $ $ sinon (et disons $ -1 $ si n est le numéro Godel d'une chaîne qui n'est pas un programme valide, juste ainsi halts () est une fonction totale sur le domaine $ mathbb n $). Alors $ mathbf { mbox {halts ()}:} mathbb n to {0,1; -1 } $.

Et disons la fonction auxiliaire INT GOBEL (char * nom de fichier) lit le contenu du fichier texte nom de fichier, renvoyant son numéro Godel. Maintenant, écrivez le petit suivant C Programmez-le et mettez-le dans le dossier DOIHALT.C

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

Donc notre Doihalt Le programme fonctionne pour toujours si halts () dit qu'il s'arrête et s'arrête immédiatement immédiatement si halts () dit qu'il fonctionne pour toujours. Ainsi, si n = Godel ("Doihalt.c") est le numéro Godel de ce programme, le seul numéro hard (n) est immédiatement incompatible. Vous n'avez même pas du tout besoin d'une séquence finie, comme dans l'exemple de @ ORLP, pour atteindre un numéro non computable.

Par calculabilité ici, cependant, nous parlons d'énumérabilité récursive, par laquelle les éléments individuels de notre ensemble d'entiers sont donnés, et la question est de savoir s'il existe ou non un programme qui les énumère tous. Pour les nombres pseudo-aléatoires générés par ordinateur, la réponse est une conclusion avant, "oui". Mais nous demandons un processus physique de boîte noire qui génére en quelque sorte le numéro après-numéro. Et après un certain temps fini, nous avons accumulé une séquence fixe de sa sortie. Nous avons donc évidemment entre nos mains tous ces chiffres - c'est la prémisse pour commencer. Et je disais, ou essayais de dire, qu'un ensemble fini de nombres que nous «avons entre nos mains» est nécessairement calculable (ce qui signifie re). Alors, comment diriez-vous cela précisément - et beaucoup plus succinctement que je ne l'ai élaboré ci-dessus?

Dans tous les cas, ma question était alors de savoir si le comportement de ce processus physique de la boîte noire est "vraiment aléatoire" - comment pourrions-nous répondre à cette question étant donné qu'une séquence finie de la sortie de la boîte (une chaîne de préfixe, pour ainsi dire ).

EDIT # 2
-------------
Le commentaire de DW sous sa réponse. D'accord, étant donné que la limite de $ $ lim_ {n à infty} f_n $ n'est pas bien définie, la caractérisation standard alternative implique une complexité algorithmique, comme suit.

Tout d'abord, pour récapituler brièvement, nous avons un processus physique de boîte noire, générant des entiers (peut-être aléatoires), $ r_i $, l'un après l'autre, dans la gamme 1 le r_i le k $. Et pour le premier $ n $ d'entre eux, $ r_1, r_2, ..., r_n $ nous construisons une fonction $ f_n (i) = r_i, i = 1 ... n $. Donc $ f_ {n + 1} $ pourrait nécessairement être très différent de $ f_n $, ou il pourrait être assez similaire.

Notez qu'un programme pour la fonction $ F_1 $ la plus simple stockerait simplement $ r_1 $ et l'imprimerait. Tout type d'algorithme pour calculer cette fonction à un numéro d'un nombre serait sûrement plus compliqué que de simplement l'imprimer. En effet, Soit $ k (f_n) $ la complexité de Kolmogorov / algorithmique de (le programme le plus simple qui calcule) fonctionne $ f_n $. Ainsi, les premiers $ f_n $ sont probablement juste en magasin et en empreinte tous les $ R_I correspondants, i = 1 ... n $.

Mais finalement, comme $ n $ devient suffisamment grand, le stockage et l'impression ne seraient probablement pas le moyen le plus court / le plus simple de générer toutes les valeurs $ n $ nécessaires $ r_i, i = 1 ... n $. La longueur / complexité d'un algorithme serait plus courte que toutes les données nécessaires. Mais, bien sûr, c'est >> seulement si < Il existe un tel algorithme en premier lieu.

Donc, pour un générateur de nombres pseudo-aléatoires, nous savons qu'il y a un algorithme. SO $ lim_ {n to infty} k (f_n) = const $ parce que ce même algorithme calcule autant de nombres aléatoires que vous le souhaitez. Sinon, pour les séquences "vraiment aléatoires", la limite diverge car il n'y a pas d'algorithme, et il n'y a finalement aucune alternative au stockage et à l'impression de toutes les données.

Je ne sais pas si ce qui précède satisfait ou non tous (ou même certaines des objections de) ci-dessous, mais en tout cas, étant donné une "chaîne de préfixe" finie de la sortie de la boîte noire $ r_i, i = 1 .. .n $, vous ne pouvez toujours pas dire (je ne pense pas) si ce $ k ( cdot) $ limite converge.