Générateur de nombres vraiment aléatoire: calculable?

Je cherche une réponse définitive à la question de savoir si la génération de nombres "réellement aléatoires" est calculable par Turing. Je ne sais pas comment formuler cela avec précision. Cette question de StackExchange sur les "algorithmes efficaces pour la génération de nombres aléatoires" est proche de répondre à ma question. Charles Stewart dit dans sa réponse, "le [caractère aléatoire de Martin-Löf] ne peut pas être généré par une machine". Selon Ross Snider, "aucun processus déterministe (tel que Turing / Register Machines) ne peut produire de nombres aléatoires" philosophiques "ou" vrais "". Existe-t-il une notion claire et acceptée de ce qui constitue un véritable générateur de nombres aléatoires? Et si oui, sait-on qu'il ne peut pas être calculé par une machine de Turing?

Peut-être me diriger vers la littérature pertinente suffirait-il. Merci pour toute l'aide que vous pourrez fournir!

Modifier. Merci à Ian et Aaron pour leurs réponses avisées! Je suis relativement peu scolarisé dans ce domaine et je suis reconnaissant pour l'aide. Si je peux prolonger un peu la question dans cet addenda: est-il vrai qu'une MT ayant accès à une source purement aléatoire (un oracle?) Peut calculer une fonction qu'une MT classique ne peut pas?

Je participe à la discussion assez tard, mais je vais essayer de répondre à plusieurs questions qui ont été posées plus tôt.

Tout d’abord, comme l’a observé Aaron Sterling, il est important de décider d’abord de ce que nous entendons par des nombres "vraiment aléatoires", et en particulier si nous examinons les choses du point de vue de la complexité ou de la calculabilité.

Cependant, permettez-moi de dire que, dans la théorie de la complexité, les gens s'intéressent principalement au pseudo- hasard, et aux générateurs pseudo -aléatoires, c'est-à-dire des fonctions allant de chaînes en chaînes, de sorte que la distribution des séquences de sortie ne peut être séparée de la distribution uniforme par un processus efficace . (où plusieurs significations d’ efficace peuvent être envisagées, par exemple calculable polytime, circuits de taille polynomiale, etc.). C'est un domaine de recherche magnifique et très actif, mais je pense que la plupart des gens s'accorderont pour dire que les objets qu'il étudie ne sont pas vraiment aléatoires, il suffit qu'ils aient l' air aléatoire (d'où le terme "pseudo").

Dans la théorie de la calculabilité, un consensus s'est dégagé sur ce qui devrait être une bonne notion de "véritable hasard", et c'est bien la notion de hasard de Martin-Löf qui a prévalu (d'autres ont été proposées et sont intéressantes à étudier mais ne portent pas tout les belles propriétés Martin-Löf aléatoire a). Pour simplifier les choses, nous allons considérer le caractère aléatoire pour des séquences binaires infinies (d’autres objets tels que des fonctions allant de chaînes en chaînes peuvent facilement être codés par cette séquence).

Une séquence binaire infinie est aléatoire de Martin-Löf si aucun processus calculable (même si nous permettons à ce processus de pouvoir être calculé en triple temps exponentiel ou plus) peut détecter un défaut d’aléatoire.$\alpha$

(1) Qu'entendons-nous par "défaut de caractère aléatoire"? Cette partie est facile: il est un ensemble de mesure 0, soit une propriété que presque toutes les séquences n'ont pas (ici on parle de Lebesgue mesurer à- dire la mesure où chaque bit a une pour être probabilité $1/2$$0$ indépendamment de tous les autres morceaux). Un exemple d'une telle faille est "avoir asymptotiquement 1/3 de zéros et 2/3 de ceux", ce qui constitue une violation de la loi des grands nombres. Un autre exemple est "pour chaque n, les 2n premiers bits de sont parfaitement distribués (autant de zéros que de zéros)". Dans ce cas, la loi des grands nombres est satisfaite, mais pas le théorème de la limite centrale. Etc.$\alpha$
(2) Comment un processus calculable peut-il tester qu'une séquence n'appartient pas à un ensemble particulier de la mesure 0? En d’autres termes, quels ensembles de mesures 0 peuvent être décrits de manière calculable? C'est précisément ce sur quoi portent les tests de Martin-Löf. Un test de Martin-Löf est une procédure calculable qui, étant donné une entrée k, peut être calculée (c'est-à-dire via une machine de Turing à entrée ) génère une séquence de chaînes w k , 0 , w k - $k$$w_{k,0}$ , ... tels que l'ensemble U k de suites infinies commençant par l'un de ceux w k , i mesure au plus$w_{k,1}$$U_k$$w_{k,i}$$2^{-k}$(Si vous aimez la topologie, notez qu'il s'agit d'un ensemble ouvert dans la topologie du produit pour l'ensemble des séquences binaires infinies). Alors l'ensemble a la mesure 0 et est appelé zéro de Martin-Löf . Nous pouvons maintenant définir le caractère aléatoire de Martin-Löf en disant qu'une séquence binaire infinie α est aléatoire de Martin-Löf si elle n'appartient à aucun jeu nul de Martin-Löf . $G=\bigcap_k U_k$$0$$\alpha$

Cette définition peut sembler technique mais elle est largement acceptée comme étant la bonne pour plusieurs raisons:

• il est suffisamment efficace, c'est-à-dire que sa définition implique des processus calculables
• il est assez fort: toute propriété "presque sûre" que vous pouvez trouver dans un manuel de théorie des probabilités (loi des grands nombres, loi du logarithme itéré, etc.) peut être testée par un test de Martin-Löf (bien que cela soit parfois difficile à prouver)
• il a été proposé indépendamment par plusieurs personnes utilisant différentes définitions (notamment la définition de Levin-Chaitin utilisant la complexité de Kolmogorov); et le fait qu'ils conduisent tous au même concept suggère que ce devrait être la bonne notion (un peu comme la notion de fonction calculable, qui peut être définie via les machines de Turing, les fonctions récursives, le lambda-calcul, etc.)
• la théorie mathématique derrière c'est très agréable! voir les trois excellents livres Une introduction à la complexité de Kolmogorov et à ses applications (Li et Vitanyi), Aléatoire algorithmique et complexité (Downey et Hirschfeldt) Computabilité et aléatoire (Nies).

À quoi ressemble une séquence aléatoire de Martin-Löf? Eh bien, prenez une pièce parfaitement équilibrée et commencez à la retourner. À chaque retournement, écrivez un 0 pour les têtes et un 1 pour les queues. Continuez jusqu'à la fin des temps. Voilà à quoi ressemble une séquence de Martin-Löf :-)

Revenons maintenant à la question initiale: existe-t-il un moyen informatique de générer une séquence aléatoire de Martin-Löf? Intuitivement, la réponse devrait être NON , car si nous pouvons utiliser un processus calculable pour générer une séquence , nous pouvons certainement utiliser un processus calculable pour décrire le singleton { α }, donc α n'est pas aléatoire. Formellement, cela se fait comme suit. Supposons qu'une séquence α soit calculable. Considérez le test de Martin-Löf suivant: pour tout k , indiquez simplement le préfixe a k de α de longueur k , et rien d’autre. Cela a au plus la mesure (en fait, exactement) 2 - $\alpha$$\alpha$$\alpha$$\alpha$$k$$a_k$$\alpha$$k$$2^{-k}$, et l'intersection des ensembles comme dans la définition est exactement { α }. CQFD !!$U_k$${\alpha}$

En fait, une séquence aléatoire de Martin-Löf est incompatible avec un sens beaucoup plus fort: si un calcul d’oracle avec oracle β (qui est lui-même une séquence binaire infinie) peut calculer α , alors pour n , n - O ( 1 ) bits de Il faut β pour calculer les n premiers bits de α (il s’agit en fait de caractériser le caractère aléatoire de Martin-Löf, ce qui est malheureusement rarement indiqué comme dans la littérature).$\alpha$$\beta$$\alpha$$n$$n-O(1)$$\beta$$n$$\alpha$

Ok, maintenant la partie "modifier" de la question de Joseph: est-il vrai qu'une MT ayant accès à une source purement aléatoire (un oracle?) Peut calculer une fonction qu'une MT classique ne peut pas?

Du point de vue de la calculabilité, la réponse est "oui et non". Si vous avez accès à une source aléatoire en tant qu'oracle (où la sortie est présentée comme une séquence binaire infinie), avec la probabilité 1, vous obtiendrez un oracle aléatoire de Martin-Löf et, comme nous l'avons vu précédemment, aléatoire de Martin-Löf implique calculable, il suffit donc de sortir l'oracle lui-même! Ou si vous voulez une fonction , vous pouvez considérer la fonction f qui pour tout n vous dit combien il y a de zéros parmi les n premiers bits de votre oracle. Si l'oracle est aléatoire de Martin-Löf, cette fonction sera non calculable.$f: \mathbb{N} \rightarrow \mathbb{N}$$f$$n$$n$

Mais bien sûr, vous pourriez soutenir que c'est de la triche: en effet, pour un oracle différent, nous pourrions avoir une fonction différente, il y a donc un problème de non-reproductibilité. Une autre façon de comprendre votre question est donc la suivante: existe-t-il une fonction non calculable, mais qui peut être "calculée avec une probabilité positive", en ce sens qu’il existe une machine de Turing avec accès à un oracle aléatoire qui, avec une probabilité positive (sur l'oracle), calcule f . La réponse est non, en raison d'un théorème de Sacks dont la preuve est assez simple. En réalité, Robin Kothari lui a principalement répondu: si la probabilité que la MT soit correcte est supérieure à 1/2, alors on peut rechercher tous les n calculs possibles de Oracle avec entrée $f$$f$$n$$n$et trouver le résultat qui obtient le "vote à la majorité", c’est-à-dire qui est produit par un ensemble d’oracles de mesure supérieur à 1/2 (ceci peut être fait efficacement). L'argument étendre même à des probabilités plus petites: supposons que les sorties de MT avec une probabilité ε > 0 . Par le théorème de densité de Lebesgue, il existe une chaîne finie σ telle que si nous fixons les premiers bits de l'oracle d'être exactement σ , puis obtenir les autres bits au hasard, puis on calcule f avec une probabilité d' au moins 0,99. En prenant un tel σ , nous pouvons appliquer à nouveau l'argument ci-dessus.$f$$\epsilon >0$$\sigma$$\sigma$$f$$\sigma$

Il y a peut-être une distinction à faire entre "calculable de Turing" et "effectivement calculable" afin de répondre à votre question. Si l'on définit "processus aléatoire" comme "un processus qui ne peut être prédit, quelles que soient les ressources dont nous disposons", alors qu'un "processus déterministe" est défini comme "processus prévisible, compte tenu de l'entrée et de l'accès à (peut-être beaucoup) de ressources, "alors aucune fonction calculable de Turing ne peut être aléatoire, car si nous connaissions la machine de Turing et la simulions, nous pourrions toujours prédire le résultat de la prochaine" expérience "du processus.

Dans ce cadre, un test de Martin-Lof peut être considéré comme un processus déterministe et la définition d'une séquence aléatoire est précisément une séquence dont le comportement n'est prédite par aucun processus calculable / déterministe de Martin-Lof / Turing.

Cela pose cependant la question suivante: "Une séquence aléatoire est-elle effectivement calculable, dans la vie réelle?" En fait, il y a une industrie ici. Il existe des CD publiés contenant des milliards de bits aléatoires (?) Et utilisés pour effectuer des simulations informatiques de systèmes physiques, etc. Ces CD garantissent que leurs séquences de bits passent un tas de tests de Martin-Lof. Le livre La promenade de l'ivrogne: Comment le hasard règne sur notre vie donne une explication pop-sci de ce problème, de manière plus détaillée.

Point non pertinent: j'apprécie votre chronique. :-)

Intuitivement, "aléatoire" signifie "imprévisible" et toute séquence générée par une machine de Turing peut être prédite en exécutant la machine. Par conséquent, les machines de Turing ne peuvent pas produire de nombres "réellement aléatoires". Il existe un certain nombre de définitions formelles de séquences aléatoires (le caractère aléatoire n’a vraiment de sens que lorsque la longueur d’une chaîne va à l’infini), qui sont toutes essentiellement équivalentes. Le plus naturel de ceux-ci est probablement le caractère aléatoire de Martin-Lof, ce qui signifie qu'une séquence réussit tous les tests statistiques calculables possibles pour la stochasticité et le caractère aléatoire de Chaitin, qui signifie que toutes les sous-séquences initiales sont incompressibles (plus spécifiquement, ont une complexité de Kolmogorov élevée). Dans ces deux définitions, il est incompatible de générer et de reconnaître les séquences aléatoires. Voir le livre "Information et Aléatoire:

Quiconque considère des méthodes arithmétiques pour produire des chiffres aléatoires est, bien sûr, dans un état de péché. Comme on l’a souligné à plusieurs reprises, il n’existe pas de nombre aléatoire: il n’existe que des méthodes permettant de produire des nombres aléatoires, et une procédure arithmétique stricte n’est bien sûr pas une telle méthode. - John von Neumann

Il semble que personne n’a répondu à votre addenda, alors je vais essayer:

Si je peux prolonger un peu la question dans cet addenda: est-il vrai qu'une MT ayant accès à une source purement aléatoire (un oracle?) Peut calculer une fonction qu'une MT classique ne peut pas?

Je vais essayer de préciser la question, puis d'y répondre. (Ma version n'est peut-être pas celle que vous aviez à l'esprit, alors laissez-moi savoir si ce n'est pas le cas.)

Nous avons une MT déterministe avec accès à un générateur de nombres aléatoires. Cette MT calcule maintenant une fonction (une fonction réelle, c'est-à-dire une carte déterministe d'un espace d'entrée vers un espace de sortie) en utilisant le générateur de nombres aléatoires d'une manière ou d'une autre.

La MT avec accès au hasard est-elle autorisée à commettre une erreur? Si ce n'est pas le cas, le DTM doit donner la réponse correcte, quels que soient les bits aléatoires fournis. Dans ce cas, les bits aléatoires sont inutiles, car vous pourriez simplement prendre la chaîne aléatoire comme étant 00000 ...

$f_i(x,r)$$f_i$$r$ et voir quelle est la sortie majoritaire et la sortir.

En ce qui concerne votre "question de montage": le fait que vous posiez des questions sur la calculabilité ou la complexité ait une grande incidence. S'il existe des limites de complexité sur la MT, vous obtenez le modèle dit aléatoire d'oracle . Si le TM peut utiliser des ressources arbitrairement grandes, mais finies, alors vous êtes dans le monde de l'aléatoire relatif : il existe des hiérarchies aléatoires d'oracles, tout comme des degrés de Turing. (Point secondaire: l'une des critiques (les plus célèbres) de Koblitz et Menzes concernait l'utilisation du modèle aléatoire d'Oracle. Votre méta-question a donc trait aux récents débats universitaires.)

J'essaie encore de comprendre votre question modifiée, en particulier les limites que vous imposez à la MT. Ainsi, bien que cette réponse puisse ne pas donner exactement ce que vous voulez, cela aidera peut-être à préciser un peu les choses.

Nous savons qu'il existe un résultat impossibilité inconditionnel d'approcher de manière déterministe le volume d'un corps convexe avec un facteur sous-exponentiel (il s'agit d'un résultat ancien de Bárány et Füredi ). En revanche, nous pouvons obtenir un FPRAS pour ce problème en utilisant l'échantillonnage. Est-ce un exemple de la séparation que vous recherchez?