NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 25/07/2017 Orientation générale  DicoMot Math Atlas Références M'écrire Barre de recherche DicoCulture Index alphabétique
	Suites & Séries
Débutants Général	CLASSIQUES				Glossaire Suites
INDEX Suites	Général		Harmonique	Suite aliquote
	Typiques		De Farey	Séquences numériques
	1 / (1 - x)		De Martin-Löf	Thue Morse
	x^k / (x^k – 1)		Engel
		Sommaire de cette page >>> Suite de CHAMPERNOWNE et de MARTIN LÖF >>> Complexité de KOLMOGOROV >>> Nombres incompressibles >>> Bio Kolmogorov >>> Bio Champernowne >>> Bio Martin-Löf

SUITE de CHAMPERNOWNE et de MARTIN LÖF

Suite "normale" Suite dans laquelle une séquence de plus en plus longue apparaît de moins en moins souvent, et, bien sûr, une séquence donnée ne se retrouve jamais indéfiniment. Un nombre réel x est normal en base b si, toutes les séquences de chiffres possibles apparaissent avec la même probabilité dans son écriture en base b. Exemple Si le 8 apparaît une fois sur 10, on dit que sa fréquence limite est 1 / 10; Si le 23, une fois sur 100: Flim = 1 / 100; Si le 555 , une fois sur mille: Flim = 1 / 1000; Etc. Construction: 01234567891011121314151617181920212223... Dans la quête d'une suite désordonnée, ici encore, la succession des chiffres n'est pas périodique, Voir Suite de Thue Morse Mais la règle de construction est simple: la suite n'est pas désordonnée. En fait, Tout nombre normal en base 10 est irrationnel. Ils semblent tous désordonnés, mais la suite ci-dessus est un contre-exemple. Note: On ne sait pas si la suite des chiffres de Pi, en base 2, est normale; Même si on le constate sur tous les chiffres connus. Paradoxe: En fait, presque toutes les suites sont aléatoires, comme l'a montré Martin Löf en 1965, selon sa définition. Mais on ne peut en définir aucune par algorithme. Elles sont partout, mais on ne peut jamais les toucher. Cette définition (très complexe, en fait!) dit, en gros, qu'une suite binaire est aléatoire si elle est incompressible. Elle s'appuie sur la théorie de la complexité de Kolmogorov. La mesure de la complexité c'est la taille du plus petit programme qui permet d'imprimer l'objet en question. Exemple: La longueur du plus petit programme pour imprimer le premier million de chiffres en base 2 de Pi est probablement supérieure à 100 lignes, mais très nettement inférieure à un million. Dans cet exemple, la taille du programme est inférieure à celle de l'objet à imprimer: il y a compression de l'information. Note: Selon cette définition, les fonctions "random" ( = hasard) des ordinateurs, engendrées par programmes ne peuvent être qu'imparfaitement aléatoires au sens de la définition de Martin Löf. Le hasard reste le hasard. On ne peut pas le formaliser!

Complexité de Kolmogorov

Complexité de Kolmogorov ou complexité aléatoire, ou complexité algorithmique C'est la complexité d'un nombre ou une suite quelconque de caractères quantifiée par la taille du programme (ou algorithme) le plus petit nécessaire pour les décrire. La référence étant une machine universelle comme la machine de Turing. Une machine universelle peut émuler n'importe quelle autre machine informatique. En gros, c'est la taille du plus petit programme écrit pour la machine universelle qui engendre la suite considérée. Exemple 1: un cercle n'est pas complexe puisque le programme pour le décrire est aussi simple que: Avance d'un pas en longueur; Tourne d'un pas en angle; Arrêt si tu te retrouves au point de départ. Exemple 2: une fractale de Mandelbrot n'est pas complexe puisque le programme pour le décrire est aussi simple que: Pour chaque point du plan calcule z²n+1 = z²n + C en complexe; si cette suite converge dessinez un point noir; sinon mettre un point de couleur selon la vitesse de divergence.

Nombres incompressibles

Voir nombres Univers et nombres incompressibles Nombre réel incompressible au sens de Kolmogorov: Tel que son développement p-adique, ou plus simplement binaire est comparable à la taille de l'algorithme qui permet de le calculer. Tous les rationnels et certains irrationnels sont compressibles, en particulier les nombres transcendants comme π, e ou 0,12345678910111213… dont le développement binaire est infini mais la suite des décimales parfaitement calculable. Le nombre oméga () de Chaitin ne l'est pas.

Voir Entropie de l'information

Andrei Kolmogorov (1903-1987)

Mathématicien soviétique et russe Il a contribué à résoudre le 13e problème de Hilbert: toute fonction de deux variables peut s'écrire comme somme de cinq fonctions de la forme F(g(x) + h(x)) où n'interviennent que des fonctions d'une variable et la somme. Il a donné une définition de la complexité. Autres domaines: la formalisation de la théorie des probabilités, la théorie algorithmique de l'information, les systèmes dynamiques, dont le théorème KAM dans les années 1950, la topologie, la logique intuitionniste les séries de Fourier, la turbulence et la mécanique classique.

Voir Contemporains

David Champernowne (1912-2000)
Mathématicien anglais. Statistiques; Nombres normaux; Constantes de Champernowne: C10 = 0,12345678910111213141516… C2 = 0,11011100101110111 … Non périodiques mais non aléatoires, ils sont irrationnels. Programme d'échecs (avec Alan Turing).

Per Martin-Löf (1942-)
Mathématicien suédois, logicien et philosophe. Définition des suites aléatoires; Théorie des types intuitionnistes; Axiome de choix.

Suite	Suite de Thue Morse Spectre numérique d'un nombre
Voir	Calcul mental Conjecture de Syracuse Énigmes en séquence Jeux – Index Pannumérique Séquences numériques Série 1 + 2x + 3x² + ... Suite de la copie augmentée Suite qui rend fou Suites fractales Théorie des nombres – Index Triangle de Leibniz
DicoNombre	Curiosité avec 1 2 3 4…
Site	La complexité mesurée … - Jean-Paul Delahaye Définir et mesurer la complexité – La théorie algorithmique de l'information – Jean-Paul Delahaye Complexité de Kolmogorov – Bruno Durand et Alexander Zvonkin
Cette page	http://villemin.gerard.free.fr/Wwwgvmm/Suite/Suitmarti.htm