séquence aléatoire algorithmique

La définition originale de Martin-Löf d'une suite aléatoire s'appuyait sur les couvertures nulles constructives ; il définissait une suite comme aléatoire si elle n'appartenait à aucune de ces couvertures. Gregory Chaitin , Leonid Levin et Claus Peter Schnorr ont démontré une caractérisation en termes de complexité algorithmique : une suite est aléatoire s'il existe une borne uniforme sur la compressibilité de ses segments initiaux. Schnorr a proposé une troisième définition équivalente en termes de martingales . L'ouvrage de Li et Vitanyi, *An Introduction to Kolmogorov Complexity and Its Applications*, constitue l'introduction de référence à ces concepts.

• Complexité algorithmique (Chaitin 1969, Schnorr 1973, Levin 1973) : La complexité algorithmique (également appelée complexité de Kolmogorov sans préfixe ou complexité de taille de programme) peut être vue comme une borne inférieure de la compressibilité algorithmique d'une séquence finie (de caractères ou de chiffres binaires). Elle associe à chaque séquence w un entier naturel K(w) qui, intuitivement, mesure la longueur minimale d'un programme informatique (écrit dans un langage de programmation donné) ne prenant aucune entrée et produisant w lors de son exécution. Étant donné un entier naturel c et une séquence w , on dit que w est c -incompressible si

Une suite infinie S est aléatoire au sens de Martin-Löf si et seulement s'il existe une constante c telle que tous S soient c -incompressibles. Plus succinctement,.

• Couvertures nulles constructives (Martin-Löf 1966) : Il s'agit de la définition originale de Martin-Löf. Pour une chaîne binaire finie w, on note C_{_w} le cylindre engendré par w . C'est l'ensemble de toutes les suites infinies commençant par w , qui est un ouvert de base dans l'espace de Cantor . La mesure produit μ( C_{_w} ) du cylindre engendré par w est définie comme 2 ^{− | w |} . Tout ouvert de l'espace de Cantor est l'union d'une suite dénombrable d'ouverts de base disjoints, et la mesure d'un ouvert est la somme des mesures de toute suite de ce type. Un ouvert effectif est un ouvert qui est l'union de la suite d'ouverts de base déterminée par une suite récursivement énumérable de chaînes binaires. Une couverture nulle constructive , ou ensemble de mesure effectif 0 , est une suite récursivement énumérable de chaînes binaires.i . Chaque couverture nulle effective détermine un de mesure 0, à savoir l'intersection des ensembles

Une séquence est dite aléatoire au sens de Martin-Löf si elle n'est contenue dans aucun intervalle quelconque.

• Martingales constructives (Schnorr 1971) : Une martingale est une fonctionw ,a et b . On appelle cela la « condition d'équité » : si une martingale est considérée comme une stratégie de pari, alors la condition ci-dessus exige que le parieur joue contre des cotes équitables. Une martingale d est dite performante sur une séquence S siLes n premiers bits de S sont . Une martingale d est constructive (également appelée faiblement calculable , semi-calculable inférieure ) s'il existe une fonction calculablew

1. t ,

Une séquence est aléatoire au sens de Martin-Löf si et seulement si aucune martingale constructive ne réussit sur elle.

La caractérisation de la complexité de Kolmogorov traduit l'intuition qu'une séquence aléatoire est incompressible : aucun préfixe ne peut être produit par un programme beaucoup plus court que le préfixe.

La caractérisation par couverture nulle traduit l'intuition qu'un nombre réel aléatoire ne devrait posséder aucune propriété « rare ». Chaque ensemble de mesure 0 peut être vu comme une propriété rare. Une suite ne peut appartenir à aucun ensemble de mesure 0, car tout ensemble à un point est de mesure 0. L'idée de Martin-Löf était de restreindre la définition aux ensembles de mesure 0 qui sont effectivement descriptibles ; la définition d'une couverture nulle effective détermine une collection dénombrable d'ensembles de mesure 0 effectivement descriptibles et définit une suite comme aléatoire si elle n'appartient à aucun de ces ensembles de mesure 0 particuliers. Puisque l'union d'une collection dénombrable d'ensembles de mesure 0 est de mesure 0, cette définition conduit immédiatement au théorème selon lequel il existe un ensemble de mesure 1 de suites aléatoires. Notons que si l'on identifie l'espace de Cantor des suites binaires à l'intervalle [0,1] des nombres réels, la mesure sur l'espace de Cantor coïncide avec la mesure de Lebesgue .

Un ensemble de mesure effective 0 peut être interprété comme une machine de Turing capable de déterminer, étant donné une chaîne binaire infinie, si cette chaîne semble aléatoire à des niveaux de signification statistique . Cet ensemble est l'intersection d'ensembles décroissants.

La caractérisation par les martingales traduit l'intuition qu'aucune procédure efficace ne devrait permettre de gagner de l'argent en pariant contre une séquence aléatoire. Une martingale d est une stratégie de pari. d lit une chaîne finie w et parie de l'argent sur le bit suivant. Elle parie une partie de son argent sur le fait que le bit suivant sera 0, et le reste sur le fait qu'il sera 1. d double sa mise sur le bit effectivement obtenu et perd le reste. d ( w ) représente le montant d'argent dont elle dispose après avoir vu la chaîne w . Puisque la mise placée après avoir vu la chaîne w peut être calculée à partir des valeurs d ( w ), d ( w0 ) et d ( w1 ), calculer le montant d'argent disponible est équivalent à calculer la mise. La caractérisation par les martingales stipule qu'aucune stratégie de pari implémentable par un ordinateur (même au sens faible des stratégies constructives, qui ne sont pas nécessairement calculables ) ne peut permettre de gagner de l'argent en pariant sur une séquence aléatoire.

Puisque chaque définition équivalente d'une suite aléatoire de Martin-Löf repose sur ce qui est calculable par une machine de Turing, on peut naturellement se demander ce qui est calculable par une machine oracle de Turing . Pour un oracle A fixé , une suite B qui est non seulement aléatoire mais qui, de plus, satisfait les définitions équivalentes de calculabilité par rapport à A (par exemple, aucune martingale constructive par rapport à l'oracle A ne réussit sur B ) est dite aléatoire par rapport à A. Deux suites, bien qu'aléatoires en elles-mêmes, peuvent contenir des informations très similaires, et par conséquent, aucune ne sera aléatoire par rapport à l'autre. Dès lors qu'il existe une réduction de Turing d'une suite à une autre, la seconde suite ne peut être aléatoire par rapport à la première, de même que les suites calculables ne sont pas aléatoires ; en particulier, cela signifie que Ω de Chaitin n'est pas aléatoire par rapport au problème de l'arrêt .

Un résultat important concernant l'aléatoire relatif est le théorème de van Lambalgen , qui stipule que si C est la séquence composée de A et B en entrelaçant le premier bit de A , le premier bit de B , le deuxième bit de A , le deuxième bit de B , et ainsi de suite, alors C est algorithmiquement aléatoire si et seulement si A est algorithmiquement aléatoire, et B est algorithmiquement aléatoire par rapport à A. Une conséquence étroitement liée est que si A et B sont tous deux aléatoires, alors A est aléatoire par rapport à B si et seulement si B est aléatoire par rapport à A.

L'aléatoire relatif nous donne la première notion plus forte que l'aléatoire de Martin-Löf, à savoir l'aléatoire par rapport à un oracle fixe A. Pour tout oracle, cette notion est au moins aussi forte, et pour la plupart des oracles, elle est strictement plus forte, puisqu'il existera des séquences aléatoires de Martin-Löf qui ne sont pas aléatoires par rapport à l'oracle A. Parmi les oracles importants souvent considérés figurent le problème de l'arrêt,n -ième saut,n -aléatoire ; une suite est donc 1-aléatoire si et seulement si elle est aléatoire au sens de Martin-Löf. Une suite n -aléatoire pour tout n est dite arithmétiquement aléatoire. Les suites n -aléatoires apparaissent parfois lorsqu'on considère des propriétés plus complexes. Par exemple, il n'existe qu'une infinité dénombrable de suites n-aléatoires.

De plus, plusieurs notions d'aléatoire sont plus faibles que l'aléatoire de Martin-Löf. Parmi celles-ci, on trouve l'aléatoire faible de type 1, l'aléatoire de Schnorr, l'aléatoire calculable et l'aléatoire partiellement calculable. Yongge Wang a démontré que l'aléatoire de Schnorr diffère de l'aléatoire calculable. Par ailleurs, l'aléatoire de Kolmogorov-Loveland n'est pas plus fort que l'aléatoire de Martin-Löf, mais on ignore s'il est en réalité plus faible.

À l'autre extrémité du spectre de l'aléatoire se trouve la notion d' ensemble K-trivial . Ces ensembles sont anti-aléatoires en ce sens que tout segment initial est logarithmiquement compressible (c'est-à-dire,