NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 20/04/2014

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

xk / (xk – 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 = n + C en complexe;

si cette suite converge dessinez un point noir;

sinon mettre un point de couleur selon la vitesse de convergence.
 

 

 

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

*    JeuxIndex

*    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 nombresIndex

*    Triangle de Leibniz

DicoNombre

*    Curiosité avec 1 2 3 4…

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Suite/Suitmarti.htm