Un sympathique visiteur de ce site a envoyé un petit message comme quoi il n'avait "rien compris" à cette énigme. Donc, voilà un petit texte histoire d'entretenir un peu la confusion.
"Le monde se divise en deux catégories, ceux qui ont un pistolet chargé et ceux qui creusent", disait Blondin. Hé bien ici, on va diviser l'ensemble des entiers naturels ({0,1,2,....}, également noté N) en deux catégories : ceux qui peuvent être décrits en moins de 10 secondes, et les autres.
Pour dramatiser un peu, mettons-nous en situation : tu dois choisir un code numérique, un entier naturel, pour verrouiller le coffre-fort contenant ton immense fortune, et ce code tu vas devoir le révéler à ton fils pour qu'il puisse l'ouvrir à ta mort, laquelle approche à grand pas (c'est comme ça). Mais ton fils est en voyage très très loin, tu ne peux communiquer avec lui que par un téléphone sécurisé, et malheureusement il ne reste que 10 secondes de forfait. Les entiers naturels peuvent alors être classés en deux catégories (plus précisément partitionnés en deux sous-ensembles), d'une part ceux qui pourront servir de code, i.e. communicables en moins de 10 secondes, d'autre part les autres.
Ainsi, par "description", ici, on entend une ou plusieurs expressions ou phrases, le tout possédant une certaine durée d'énonciation (oui on peut parler super vite, mais il faut que ce soit intelligible quand même), définissant de façon unique un entier naturel. Une description assez simple (en terme de description) d'un entier est sa prononciation. En effet, un entier est une entité abstraite (?), et son nom le caractérise sans équivoque. Il découle de ceci que chaque entier naturel admet au moins une description, quitte à faire continuer la description par quelqu'un d'autre au bout de quelques décennies. Le langage de description n'est pas important, il peut être vu comme un système de coordonnées.
Bref, on a défini une description, comme on aurait pu définir les programmes informatiques qui prennent en argument une chaîne de caractères et renvoient un entier (P: S->N), les programmes informatiques qui ne prennent pas d'argument et renvoient un entier (P: V->N), et plein d'autres choses.
En moins de dix secondes, il y a plein de nombres qu'on peut expliciter de façon univoque, que ce soit par une description directe (ex : "26", "3 fois 3", "10 puissance cent milliards"), ou indirecte (ex : "le plus petit entier naturel").
Par contre, il y a des nombres qu'on ne peut pas décrire en moins de 2 secondes. Ainsi, lecteur, va décrire
251959084756578934940271832400483985714292821262040320277771378360436620207075
955562640185258807844069182906412495150821892985591491761845028084891200728449
926873928072877767359714183472702618963750149718246911650776133798590957000973
304597488084284017974291006424586918171951187461215151726546322822168699875491
824224336372590851418654620435767984233871847744479207399342365848238242811981
638150106748104516603773060562016196762561338441436038339044149526344321901146
575444541784240209246165157233507787077498171257724679629263863563732899121548
31438167899885040445364023527381951378636564391212010397122822120720357
en moins de 10 secondes. (En fait c'est possible, avec "RSA 2048", mais bon c'est juste pour donner une idée, le vrai message étant que le sous-ensemble des nombres descriptibles en moins de dix secondes est fini.)
Un nombre possède plusieurs descriptions (en fait une infinité) ; de plus sur l'ensemble des descriptions on peut définir une relation d'ordre, en disant qu'une description est plus courte qu'une autre ssi sa durée de prononciation est inférieure à celle de l'autre. Par exemple, "8" est plus courte que "2+2+2+2", "2 puissance 20" est plus courte que "1 048 576". Tu vois déjà apparaître l'idée de "compressibilité" d'un nombre, voire d'entropie.
Il se trouve que la topologie autour de cette relation d'ordre est très différente selon que l'on considère que la durée d'une description est caractérisée un nombre positif réel (système continu) ou entier (système discret, bien ordonné en plus). Mais on va opter pour un modèle discret, et cela permet d'affirmer que tout entier naturel admet au moins une description plus courte que toutes les autres décrivant ce même entier. La durée d'une telle description sera appelée complexité descriptive (au sens de Chaitin) du nombre. De là on définit une relation d'ordre sur les nombres.
L'analogue de cette notion pour (P: S->N) est, pour un programme fixé, la longueur (disons en octets) de S ; pour (P: V->N) c'est la taille du programme lui-même qui entre en jeu.
Aux lecteurs qui sont allés jusque-là, à ceux qui avaient déjà compris tout ça - et qui ont trouvé d'ailleurs que décidément c'était très mal expliqué ici, à ceux qui ont directement sauté jusqu'à ce paragraphe, que reste-t-il à dire ? Ah, oui, qu'on peut également classifier les entiers naturels en deux catégories, ceux dont la complexité descriptive est inférieure à un million de secondes, et les autres ; que dans ce dernier ensemble il existait un plus petit élément dont la description univoque a étrangement été lue ici même en moins d'un million de secondes par le courageux lecteur, et que tout ceci découle du fait que le français est un système capable de décrire les entiers naturels. L'essence de ce paradoxe, appelé paradoxe de Berry, réside dans la notion d'auto-référence pour laquelle le lecteur est renvoyé vers le livre de Douglas Hofstadter, "Gödel, Escher, Bach".
Question subsidiaire : D'accord, et, existe-t-il d'autres nombres, qu'on ne peut pas définir à l'aide de la langue française ?
Ho, ça suffit pour aujourd'hui, d'acc ? Si ce genre de choses t'intéresse, hé bien il y en a qui sont payés pour faire des conférences là-dessus ; tu peux aller voir le site de Gregory Chaitin.
The greatest trick the devil ever pulled
was convincing the world he didn't exist.
Jusque là il a été question de l'existence d'un élément maximal dans l'ensemble des entiers descriptibles en N secondes (ainsi l'ensemble des entiers descriptibles par l'humanité durant son existence est majoré), mais il n'a pas été donné l'occasion d'expliciter un tel élément. Déterminer ainsi le plus grand élément d'une complexité donnée est une tâche délicate. Pour simplifier on peut se chercher à la place le plus grand entier descriptible avec N bits, ou le plus grand entier calculable avec N bits (est-ce la même chose ?) . La bonne nouvelle, c'est que Scott Aaronson a déjà écrit un texte sur le sujet des grands nombres où cette problématique est abordée. Dans ce contexte est introduite la suite d'Ackermann, vue comme une "procession d'opérations arithmétiques, chacune étant plus puissante que la précédente" (addition, multiplication, exponentiation, 'tétration', etc). Il est possible que ce genre d'approche récursive soit à comparer avec la construction des ordinaux selon Von Neumann (vue comme une procession d'ordinaux), telle une échelle s'engouffrant dans les vertiges de l'infini. Est également décrite la suite des Castors Affairés de Rado (Busy Beaver numbers), qui met en évidence les limites des notations mathématiques telles que les machines de Turing.
Pour finir, on peut signaler l'existence du documentaire "Dangerous Knowledge", produit par la BBC, évoquant les oeuvres respectives de Georg Cantor, Ludwig Boltzmann, Kurt Gödel, et Alan Turing. Les apparitions de scientifiques contemporains, entre autres Gregory Chaitin et Roger Penrose, viennent ponctuer les reconstitutions de l'histoire tourmentée de leurs découvertes.
Little Neo, january 2006, upd : dec 2007
"Le monde se divise en deux catégories, ceux qui ont un pistolet chargé et ceux qui creusent", disait Blondin. Hé bien ici, on va diviser l'ensemble des entiers naturels ({0,1,2,....}, également noté N) en deux catégories : ceux qui peuvent être décrits en moins de 10 secondes, et les autres.
Pour dramatiser un peu, mettons-nous en situation : tu dois choisir un code numérique, un entier naturel, pour verrouiller le coffre-fort contenant ton immense fortune, et ce code tu vas devoir le révéler à ton fils pour qu'il puisse l'ouvrir à ta mort, laquelle approche à grand pas (c'est comme ça). Mais ton fils est en voyage très très loin, tu ne peux communiquer avec lui que par un téléphone sécurisé, et malheureusement il ne reste que 10 secondes de forfait. Les entiers naturels peuvent alors être classés en deux catégories (plus précisément partitionnés en deux sous-ensembles), d'une part ceux qui pourront servir de code, i.e. communicables en moins de 10 secondes, d'autre part les autres.
Ainsi, par "description", ici, on entend une ou plusieurs expressions ou phrases, le tout possédant une certaine durée d'énonciation (oui on peut parler super vite, mais il faut que ce soit intelligible quand même), définissant de façon unique un entier naturel. Une description assez simple (en terme de description) d'un entier est sa prononciation. En effet, un entier est une entité abstraite (?), et son nom le caractérise sans équivoque. Il découle de ceci que chaque entier naturel admet au moins une description, quitte à faire continuer la description par quelqu'un d'autre au bout de quelques décennies. Le langage de description n'est pas important, il peut être vu comme un système de coordonnées.
Bref, on a défini une description, comme on aurait pu définir les programmes informatiques qui prennent en argument une chaîne de caractères et renvoient un entier (P: S->N), les programmes informatiques qui ne prennent pas d'argument et renvoient un entier (P: V->N), et plein d'autres choses.
En moins de dix secondes, il y a plein de nombres qu'on peut expliciter de façon univoque, que ce soit par une description directe (ex : "26", "3 fois 3", "10 puissance cent milliards"), ou indirecte (ex : "le plus petit entier naturel").
Par contre, il y a des nombres qu'on ne peut pas décrire en moins de 2 secondes. Ainsi, lecteur, va décrire
Un nombre possède plusieurs descriptions (en fait une infinité) ; de plus sur l'ensemble des descriptions on peut définir une relation d'ordre, en disant qu'une description est plus courte qu'une autre ssi sa durée de prononciation est inférieure à celle de l'autre. Par exemple, "8" est plus courte que "2+2+2+2", "2 puissance 20" est plus courte que "1 048 576". Tu vois déjà apparaître l'idée de "compressibilité" d'un nombre, voire d'entropie.
Il se trouve que la topologie autour de cette relation d'ordre est très différente selon que l'on considère que la durée d'une description est caractérisée un nombre positif réel (système continu) ou entier (système discret, bien ordonné en plus). Mais on va opter pour un modèle discret, et cela permet d'affirmer que tout entier naturel admet au moins une description plus courte que toutes les autres décrivant ce même entier. La durée d'une telle description sera appelée complexité descriptive (au sens de Chaitin) du nombre. De là on définit une relation d'ordre sur les nombres.
L'analogue de cette notion pour (P: S->N) est, pour un programme fixé, la longueur (disons en octets) de S ; pour (P: V->N) c'est la taille du programme lui-même qui entre en jeu.
Aux lecteurs qui sont allés jusque-là, à ceux qui avaient déjà compris tout ça - et qui ont trouvé d'ailleurs que décidément c'était très mal expliqué ici, à ceux qui ont directement sauté jusqu'à ce paragraphe, que reste-t-il à dire ? Ah, oui, qu'on peut également classifier les entiers naturels en deux catégories, ceux dont la complexité descriptive est inférieure à un million de secondes, et les autres ; que dans ce dernier ensemble il existait un plus petit élément dont la description univoque a étrangement été lue ici même en moins d'un million de secondes par le courageux lecteur, et que tout ceci découle du fait que le français est un système capable de décrire les entiers naturels. L'essence de ce paradoxe, appelé paradoxe de Berry, réside dans la notion d'auto-référence pour laquelle le lecteur est renvoyé vers le livre de Douglas Hofstadter, "Gödel, Escher, Bach".
Question subsidiaire : D'accord, et, existe-t-il d'autres nombres, qu'on ne peut pas définir à l'aide de la langue française ?
Ho, ça suffit pour aujourd'hui, d'acc ? Si ce genre de choses t'intéresse, hé bien il y en a qui sont payés pour faire des conférences là-dessus ; tu peux aller voir le site de Gregory Chaitin.
The greatest trick the devil ever pulled
was convincing the world he didn't exist.
Jusque là il a été question de l'existence d'un élément maximal dans l'ensemble des entiers descriptibles en N secondes (ainsi l'ensemble des entiers descriptibles par l'humanité durant son existence est majoré), mais il n'a pas été donné l'occasion d'expliciter un tel élément. Déterminer ainsi le plus grand élément d'une complexité donnée est une tâche délicate. Pour simplifier on peut se chercher à la place le plus grand entier descriptible avec N bits, ou le plus grand entier calculable avec N bits (est-ce la même chose ?) . La bonne nouvelle, c'est que Scott Aaronson a déjà écrit un texte sur le sujet des grands nombres où cette problématique est abordée. Dans ce contexte est introduite la suite d'Ackermann, vue comme une "procession d'opérations arithmétiques, chacune étant plus puissante que la précédente" (addition, multiplication, exponentiation, 'tétration', etc). Il est possible que ce genre d'approche récursive soit à comparer avec la construction des ordinaux selon Von Neumann (vue comme une procession d'ordinaux), telle une échelle s'engouffrant dans les vertiges de l'infini. Est également décrite la suite des Castors Affairés de Rado (Busy Beaver numbers), qui met en évidence les limites des notations mathématiques telles que les machines de Turing.
Pour finir, on peut signaler l'existence du documentaire "Dangerous Knowledge", produit par la BBC, évoquant les oeuvres respectives de Georg Cantor, Ludwig Boltzmann, Kurt Gödel, et Alan Turing. Les apparitions de scientifiques contemporains, entre autres Gregory Chaitin et Roger Penrose, viennent ponctuer les reconstitutions de l'histoire tourmentée de leurs découvertes.
Little Neo, january 2006, upd : dec 2007