David Madore's WebLog

2008-04-27 (dimanche)

J'achète mes lunettes sur Internet

Étant très myope (−9 dioptries sur le contre-axe à l'œil droit), j'ai besoin de lunettes à verres amincis, voire ultra-amincis (disons, avec un indice de réfraction autour de 1.75). En France, de telles lunettes coûtent cher : on peut compter sur un gros 300€ la paire, au moins. Certains opticiens proposent deux paires pour le même prix (si on demande exactement les mêmes verres, voire la même monture), mais presque toujours on voit que cette offre est limitée aux verres non amincis (ou pas trop amincis) ou encore aux vergences dans un certain intervalle, ou encore aux non-astigmates — toujours est-il que je suis hors course. Mon père s'est récemment fait réaliser des lunettes tarif sécu, mais, là aussi, il ne faut pas compter sur des verres amincis.

La raison pour laquelle c'est aussi cher est simplement que les opticiens prennent une marge énorme (c'est aussi la raison pour laquelle ils peuvent se permettre de faire des offres deux-pour-le-prix-d'une, voire trois-pour-un-pouillème-de-plus aussi facilement). Heureusement, pour les gens qui comme moi ne tiennent pas à passer des heures à choisir leur monture, qui n'ont pas peur de recopier eux-mêmes les nombres de l'ordonnance et de mesurer la distance pupillaire, et qui achètent volontiers en ligne, il y a une solution bien pratique : les opticiens de Hong Kong !

On trouve en effet des sites Web sur lesquels acheter une paire de lunette qui sera réalisée à Hong Kong à un prix défiant toute concurrence : les deux paires de lunettes photographiées ci-dessus m'ont coûté 61.41€ pour la verte (qui a des verres amincis en polycarbonate, d'indice de réfraction 1.67) et 94.50€ pour la rouge (qui a des verres ultra-amincis minéraux, d'indice de réfraction 1.80) que j'ai achetée après m'être assurée que la première paire était satisfaisante. Précisons que ces prix incluent les frais de port et les frais de change prélevés par ma banque. Et la qualité est irréprochable : les cadres sont confortables et solides (c'est du titane), les verres n'ont pas un défaut, le traitement anti-reflet est bon, bref, je suis complètement satisfait. J'aurais également pu faire réaliser des solaires, y compris auto-obscurcissantes ou avec dégradé, des verres teintés de plusieurs couleurs amusantes, ou avec un revêtement métalisé.

Le site que j'ai choisi d'utiliser s'appelle Optical4Less, parce que c'est le seul que j'ai trouvé qui proposait effectivement les verres minéraux d'indice 1.80 (il paraît que la vente de tels verres est interdite aux États-Unis, soit dit en passant ; en France, on en trouve évidemment, mais cher) ; pour ceux que ça intéresse, c'est aussi apparemment le seul qui permet d'ajouter une correction prismatique. En contrepartie, leur choix de montures est un peu restreint : mais pour ce qui me concernait, ça allait très bien. Sinon, le méta-site GlassyEyes.com propose un certain nombre d'autres liens et des comparatifs et revues entre différents sites : 39DollarGlasses.com et EyeBuyDirect.com m'avaient l'air assez bien et assez professionnels, mais je ne garantis évidemment rien.

Pour le choix de la monture, on ne peut évidemment pas essayer : il y a la possibilité d'utiliser une petite application Flash (ou Java, je ne sais plus) pour voir les lunettes sur une photo de soi, mais, évidemment, ce n'est pas aussi bien que d'essayer en vrai. Ceci dit, je trouve que pour ce prix on peut se permettre de prendre un peu de risques — au pire ça fera une paire de rechange. Pour entrer les caractéristiques des verres, il suffit de savoir lire ce que l'ophtalmo a écrit (certes, vues les pattes de mouches de certains médecins, ce n'est pas forcément une mission facile) : la façon de noter les caractéristiques est apparemment standardisée[#] dans le monde entier, et on donne toujours l'œil droit (oculus dexter) en premier et l'œil gauche (oculus sinister) ensuite.

Il y a une chose que l'ophtalmo ne mesure pas, cependant (mais je suppose qu'il peut le faire si on lui demande), c'est la distance pupillaire. C'est quelque chose de très important, qu'il faut mesurer soigneusement, au millimètre près (voire au demi-millimètre près), si on veut que les lunettes aillent bien : il s'agit de la distance entre les centres des pupilles des deux yeux, donc entre les centres optiques des verres des lunettes (au moins pour la vision de loin ; pour la vision de près, les choses seront plus compliquées !). Pour bien la mesurer, je recommande la procédure suivante : se tenir debout devant un miroir plan vertical en faisant bien face au miroir, avec un feutre non-permanent dans la main et les anciennes lunettes sur le nez. Cacher son œil gauche avec un carton (c'est mieux que de le fermer, ça assurera qu'on ne changera pas de direction de regard), regarder dans le miroir le reflet de l'œil droit bien en face : faire un petit point avec le feutre sur le miroir et sur les anciennes lunettes. Le point doit être parfaitement au centre de l'œil. Puis, surtout sans bouger la tête (on s'en assurera en vérifiant que le point sur le miroir est toujours bien centré), cacher l'œil droit au lieu du gauche et recommencer la procédure (faire un point sur le miroir et un sur ses lunettes, au centre de l'œil gauche). Ensuite, prendre une règle et vérifier que la distance entre les points sur le miroir est exactement la même que sur les lunettes : c'est la distance optique recherchée. Si on ne trouve pas la même mesure, effacer les points et recommencer : j'aurais tendance à dire que la mesure sur le miroir est meilleure, mais il vaut mieux perdre du temps que de risquer d'avoir une mauvaise valeur. Pour tous les cas compliqués, je suppose qu'il vaut mieux demander à l'ophtalmo de faire la mesure. D'autres conseils sont donnés ici.

Une autre chose à savoir, c'est si la monture sera de la bonne taille : pour ça, il faut mesurer les dimensions de son ancienne paire et chercher une paire qui ait à peu près les mêmes. On trouvera par exemple sur cette page une explication de ce que les mesures signifient (la moins évidente étant temple length, qui désigne la longueur du bras, mesurée projetée sur son axe). Si on a un doute sur le fait qu'un cadre convienne, Optical4Less propose la possibilité d'entrer les mesures de la monture antérieure et ils choisiront une paire proche qui convienne : c'est ce que j'ai fait pour ma première paire. Mais globalement, la commande est vraiment facile[#2] à faire.

Pour le paiement, j'utilise pour ma part des numéros de carte de crédit à usage unique fournis par ma banque, donc je n'ai pas eu à m'inquiéter, mais je crois qu'on peut de toute façon avoir confiance (l'opticien ne voit pas le numéro de la carte, c'est une banque de Hong Kong qui sécurise le paiement). Quant à la livraison, elle a pris quatre semaines : ça arrive dans un tout petit paquet avec des jolis timbres de la poste de Hong Kong et qui contient juste les lunettes dans un étui basique.

[#] On donne la partie sphérique, qui est en fait la vergence selon l'axe dont la direction est indiquée (s'il y a astigmatisme) en degrés par rapport à l'horizontale, plus la partie cylindique, qui est la vergence à ajouter (algébriquement, bien sûr) selon le contre-axe c'est-à-dire la direction perpendiculaire à l'axe. Par exemple, à l'œil droit, j'ai −8.25(−0.75@130°), ce qui veut dire −8.25 dioptries sur l'axe à 130° et −9.00 dioptries sur le contre-axe à 40°. Cela pourrait aussi bien s'écrire −9.00(+0.75@40°).

[#2] Lors de ma seconde commande, j'ai eu un tout petit problème avec le site Web de Optical4Less, qui ne m'affichait pas le bouton pour continuer la commande. Je suppose que ce problème a été corrigé depuis, mais s'il ne l'a pas été c'est facile d'utilise le DOM inspector de Firefox pour rendre visible le bouton qui était simplement caché (et non absent).

Commentaires

2008-04-26 (samedi)

Fragment littéraire gratuit #110 (une mythologie)

Le panthéon ordique est présidé par la trinité majeure formée des dieux Wergiur et Kendoriun et de la déesse Volyźiar. Wergiur est généralement dépeint comme un adolescent musclé, Kendoriun comme un vieillard barbu, et Volyźiar comme une femme d'une très grande beauté, mais les théologiens s'accordent pour dire que ce n'est pas là leur figure réelle (ou en tout cas pas leur forme naturelle), seulement la façon dont on rappelle leur attribution. D'ailleurs, dans les représentations de la période préclassique, il arrive que Wergiur ou Kendoriun apparaissent sous des traits féminins, et dans les fresques à Galgoliër qui décrivent la Création, aucune divinité n'est anthropomorphe (ce sont des sphères colorées). La couleur d'un dieu, en revanche, semble une caractéristique permanente : celle associée à Wergiur est le rouge du sang, celle de Kendoriun le bleu du ciel et celle de Volyźiar le vert des jeunes pousses. Leur fonction est très largement la puissance, la connaissance et la volonté respectivement : Wergiur gouverne la force physique, mais également la réussite dans une compréhension assez étendue, Kendoriun est le dieu de la sagesse, de l'intelligence et de la justice ainsi que le scribe divin, et Volyźiar est la source des sentiments et de la beauté et la déesse de la paix (dans cette dernière attribution, elle s'oppose éventuellement à Wergiur).

Cette trinité cardinale est à la tête d'un grand nombre de divinités mineures, trop nombreuses pour être citées, généralement organisées comme faisant partie de la suite d'une des trois majeures : pourtant, cette dépendance n'est pas hiérarchique, d'ailleurs le canon précise clairement qu'aucun dieu n'a de pouvoir sur un autre. Il faut souligner que les dieux ordiques ne sont pas des créatures magiques et n'interviennent pas directement dans le monde matériel (même si cela est moins clair quand il s'agit de Wergiur ou dans la Création) : ils inspirent seulement aux hommes leurs actions, et s'ils vivent eux-mêmes des aventures qui sont parallèles à celles de l'humanité ce n'est pas qu'ils agissent mais qu'il y a une correspondance spirituelle entre le monde des dieux et celui des hommes, mondes cependant bien distincts.

Au-dessus de ces dieux pour ainsi dire « ordinaires », on trouve le Seigneur de l'Ordre, dieu de la nécessité, et le Maître du Chaos, dieu du hasard, qui sont associés aux couleurs blanche et noire. Il serait tentant de les présenter comme le dieu du bien et le dieu du mal, mais cette interprétation est incorrecte car aucune divinité ordique n'est maléfique, et en tout cas ces dieux ne sont jamais ennemis. Ils semblent placés sur un plan différent des autres dieux, dont le Seigneur de l'Ordre est parfois qualifié de père (il n'est pas clair si le Maître du Chaos a des enfants ni ce qu'ils seraient), ils n'ont pas de nom propre, sont de tout point de vue encore moins humains que les divinités inférieures, et ne faisaient d'objet d'aucun culte. Un mythe de la Création les présente comme ayant fabriqué le monde, étant eux-mêmes enfants d'un dieu créateur encore plus distant ; un théologien épiclassique suggère en fait une infinité de dieux de plus en plus élevés et de plus en plus incompréhensibles pour les hommes.

Commentaires

2008-04-23 (mercredi)

Platonisme et mathématiques

Une assez longue réflexion en philosophie des mathématiques, que j'ai écrite dans un mail à un ami, et qui me semble suffisamment intéressante pour reproduire ici : il s'agit d'éclaircir un peu la question de savoir quel sens est-ce que ça a de qualifier un énoncé mathématique de vrai ou faux ?, i.e., dans quelle mesure les objets mathématiques existent-ils ? Et notamment : pourquoi est-ce qu'on sera généralement d'accord pour attribuer la valeur de vérité vraie à l'énoncé 252097800623 est un nombre premier mais qu'on sera beaucoup plus sceptique quant au fait que l'hypothèse du continu ait vraiment un sens dans le monde réel ?

On peut établir une hiérarchie dans laquelle s'inscrivent un certain nombre d'énoncés mathématiques (mais pas tous !) en fonction de la complexité de leurs quantificateurs. (Je crois que cette hiérarchie est due, sous une forme ou une autre, à Stephen Kleene et Azriel Lévy, mais je ne sais pas exactement quelles sont les contributions de l'un et de l'autre. Il en existe un certain nombre de variantes, arithmétiques ou ensemblistes : la variante qui suit est clairement du côté arithmétique d'ordre supérieur si on doit la qualifier plus précisément : ce que j'appellerai un énoncé Π_n c'est précisément un énoncé arithmétique Π_n.)

Tout en bas de la hiérarchie, il y a les énoncés et prédicats qu'on peut indifféremment appeler Σ₀, Π₀ ou Δ₀. Il s'agit des affirmations dont tous les quantificateurs portent sur les entiers naturels et sont, de surcroît, bornés, ou gardés, c'est-à-dire sont de la forme il existe un n inférieur à t ou pour tout n inférieur à t avec t un terme en les variables libres à ce point-là (disons que le terme peut faire intervenir l'addition, la multiplication et l'exponentiation des entiers, ou peut-être n'importe quelle fonction primitive récursive, pour ce que je vais dire ce n'est pas important).

Par exemple, l'entier formé par les 10000000000 premières décimales de pi en base 10 est un nombre premier peut s'écrire sous la forme d'un énoncé Δ₀ (modulo un tout petit peu de travail sur les écritures, i.e., l'implémentation d'un algorithme qui calcule pi). L'essentiel est que quand on a affaire à une telle affirmation, on peut la tester, de façon algorithmique, en temps fini, avec terminaison garantie (pour chaque valeur des variables libres, s'il y en a) : pour les connecteurs propositionnels c'est clair, et pour les quantificateurs, comme ils sont bornés, on n'a jamais qu'un nombre fini de cas à tester ; pour la même raison, un énoncé Δ₀ n'est jamais indécidable. Ça c'est ce qui est censé justifier que, philosophiquement, à peu près tout le monde conviendra qu'il y a bien un sens à dire si un tel énoncé est vrai ou faux — il suffit d'essayer. Évidemment, comme les opinions philosophiques des gens sont très variés, il y aura des ultra-finitistes purs et durs pour me dire que d'après eux, non, ça n'a pas de sens de se demander si l'entier formé par les 10↑(10↑(10↑(10↑10))) premières décimales de pi est premier ou non, s'il est complètement inconcevable de tester aussi loin : j'appellerai ces gens des (0,0)-platoniciens (i.e., pas du tout platoniciens) ; les autres sont au moins (0,1)-platoniciens.

Juste au-delà des énoncés (et prédicats) Δ₀, il y a les énoncés (et prédicats) Σ₁ et Π₁. Les premiers sont formés en ajoutant devant un prédicat Δ₀ un quantificateur existentiel portant sur les entiers naturels, alors que les seconds ajoutent un quantificateur universel. En fait, il est assez facile de voir (en utilisant un codage des k-uplets d'entiers par des entiers) qu'on peut se permettre d'ajouter un nombre fini de quantificateurs de même nature pour le même prix. Bien sûr, la négation d'un énoncé Σ₁ est Π₁, donc pour ce qui est de donner une valeur de vérité on peut ne regarder qu'un d'entre eux.

Un énoncé Π₁ peut être réfuté par la donnée d'un contre-exemple ; en revanche, il risque de ne jamais pouvoir être confirmé de façon certaine : en effet, il y a des énoncés Π₁ qui sont indécidables (l'exemple typique étant le système T [le système qui m'intéresse et dans lequel je travaille : Peano, ZFC, que sais-je encore…] est consistant, i.e., il n'existe pas de preuve de Faux dedans, ce qui est un énoncé arithmétique Π₁ comme on s'en convainc facilement, et dont Gödel nous dit qu'il n'est pas démontrable s'il est vrai). En fait, ils sont tous équivalents à un énoncé du type la machine de Turing explicitement donnée par le programme suivant <…> va tourner sans jamais s'arrêter (par exemple une machine de Turing qui cherche une démonstration de 0=1). Pourtant, philosophiquement, on peut être d'accord qu'ils ont une valeur de vérité (dans le vrai monde, je veux dire) sur la base d'une hypothèse de pensée du genre je laisse tourner indéfiniment la machine de Turing, ce qui a un sens, et ça a donc bien un sens de se demander si elle s'arrêtera un jour, ou pas. (Tout le monde ne sera pas d'accord, évidemment.)

Beaucoup d'énoncés mathématiques importants sont arithmétiques Π₁ comme je viens de le décrire : la conjecture de Goldbach, par exemple, ou le théorème de Fermat, ou encore l'hypothèse de Riemann (c'est moins évident pour cette dernière, mais on peut encore la mettre sous cette forme). Un énoncé de la forme telle variété algébrique (définie explicitement sur ℤ) a un point entier/rationnel est Σ₁ (et Matiyasevich a montré, en gros, qu'on peut toujours ramener un énoncé Σ₁ à cette forme dans le cas entier). De façon importante, aussi, tous les énoncés du type telle affirmation est démontrable ou telle affirmation est réfutable sont Σ₁ ; et, du coup, Peano est consistant ou ZFC est consistant sont Π₁ : il est important de souligner que, même si ZFC parle d'ensembles, l'affirmation de sa consistance est un énoncé purement arithmétique, et Π₁ de surcroît. Et par ailleurs on peut aussi souligner que, en parlant d'ensembles, ZFC permet de démontrer des énoncés arithmétiques Π₁ (du style Peano est consistant) que des systèmes plus faibles (Peano, en l'occurrence) ne démontrent pas. Comme beaucoup de mathématiciens seront d'accord que la question de savoir si <truc> est un théorème a un sens, on peut en conclure qu'ils sont au moins d'accord que les énoncés arithmétiques Σ₁ et Π₁ ont une valeur de vérité : on peut donc les qualifier de (0,2)-platoniciens.

Il y a aussi les Δ₁ dans l'histoire : ce sont ceux qui peuvent s'écrire à la fois comme un Π₁ et comme un Σ₁, avec une démonstration de l'équivalence (il faut considérer que cette démonstration fait partie de la donnée de l'énoncé, pour pouvoir le qualifier de Δ₁, parce que sinon il existe une démonstration… ça va rendre le truc Σ₁, ce qui n'est pas bien). De beaucoup de points de vue, on peut considérer qu'un Δ₁ c'est aussi bien qu'un Δ₀ : en tout cas c'est finiment testable, puisqu'on essaie en parallèle de démontrer le Σ₁ et de réfuter le Π₁ et on est sûr que l'un d'entre eux terminera en temps fini.

Un énoncé ou prédicat Π_n+1 en général se forme en ajoutant un quantificateur universel (ou un nombre fini d'entre eux) devant un prédicat Σ_n, et un énoncé ou prédicat Σ_n+1 avec un quantificateur existentiel devant un prédicat Π_n. Tous ces quantificateurs portent toujours sur les entiers, pour l'instant : il s'agit d'affirmations arithmétiques du premier ordre. Bien sûr, un énoncé Δ_n c'est un énoncé qui peut se mettre sous la forme Π_n et Σ_n à la fois ; et je dirai qu'un mathématicien est au moins (0,n+1)-platonicien s'il admet que les énoncés Π_n ont une valeur de vérité bien définie.

Par exemple, un Π₂, il va dire que pour tout x il existe y tel que (une certaine propriété testable de x et de y) : c'est difficile à réfuter (il faut exhiber un x avec une démonstration du fait que pour chaque y ça ne marche pas) et encore plus difficile à prouver ; donc là j'ai encore plus de mal à justifier philosophiquement que ça a bien un sens de dire si c'est vrai ou faux. Néanmoins, si on a concédé que les énoncés Π₁ et Σ₁ sont toujours soit vrais soit faux, on peut encore admettre quelque chose sur les Π₂ (et Σ₂), avec une expérience de pensée du style : je lance une machine qui va tester tous les x et, pour chaque x, examiner tous les y — et à la fin des temps je verrai bien si elle a parcouru tous les x (auquel cas mon énoncé Π₂ est vrai) ou si elle est restée bloquée indéfiniment sur l'un d'entre eux (auquel cas l'énoncé est faux, cet x donnant un contre-exemple pour lequel il n'existe pas de y).

Exemples d'énoncés mathématiques Π₂ : toute suite finie de chiffres se trouve quelque part dans l'écriture décimale de pi ; ou encore : P n'est pas égal à NP (qu'on peut voir sous la forme il n'existe pas un algorithme et une borne polynomiale telle que l'algorithme résolve tout instance de SAT en temps donné par cette borne). Si on convient qu'un tel énoncé a un sens, on est au moins (0,3)-platoniciens (j'ai décalé les indices de 1 pour convenir qu'un (0,0)-platonicien est quelqu'un qui n'admet même pas les énoncés Δ₀). Je pense que beaucoup de mathématiciens seront encore dans ce cas. Quant à l'énoncé il n'existe pas d'algorithme permettant de dire si une variété algébrique (définie sur ℚ) admet ou non un point ℚ-rationnel, il est Π₃ si je ne m'abuse (pour toute algorithme il existe une variété telle que pour tout M l'algorithme ne finit pas en temps M et la variété n'a pas non plus de point de hauteur <M).

Une façon de voir la valeur de vérité d'un énoncé Π_n, c'est de considérer le jeu suivant à deux joueur : Forall cherche à réfuter l'énoncé, et Exists cherche à le confirmer. Le jeu n'a que n coups (c'est un jeu fini), Forall joue en premier en donnant un entier naturel, Exists réplique avec un entier naturel, et ainsi de suite sur n coups ; à la fin, on substitue ces entiers naturels aux n variables alternativement quantifiées par l'énoncé, et si le résultat (qui est finiment testable car Δ₀) est faux, Forall a gagné, sinon c'est Exists. La vérité de l'énoncé est équivalente à l'affirmation que Exists possède une stratégie gagnante, et sa fausseté au fait que Forall en a une. Donc si on admet le principe que tout jeu fini de la sorte a une stratégie gagnante, alors on admet l'idée que tout énoncé arithmétique du premier ordre a une valeur de vérité.

Une autre façon de voir les choses est de dire : si j'ai un Oracle qui me permet de décider si une machine de Turing s'arrête (donc si j'admets la possibilité conceptuelle d'un tel Oracle) alors je peux réfuter un énoncé Π₂ en utilisant cet Oracle dans une machine de Turing ; si j'ai un Oracle, encore plus puissant, qui me permet de décider si une machine de Turing pouvant faire appel au premier Oracle s'arrête, alors je peux réfuter un énoncé Π₃, etc. Si j'admets que tous ces Oracles ont un sens, alors j'admets que tout énoncé arithmétique du premier ordre a une valeur de vérité.

Quelqu'un qui admet que tout énoncé arithmétique du premier ordre (i.e., Π_n pour n'importe quel n) a une valeur de vérité, je vais le qualifier de (1,0)-platonicien (ou (1,1)-platonicien, ma numérotation étant un peu malheureuse). Personnellement je crois être (1,0)-platonicien et je ne suis pas persuadé d'être plus. Mais je vais expliquer ce que ce plus signifie.

Pour ça, il faut passer aux énoncés d'ordre supérieur, c'est-à-dire, admettant des quantificateurs non plus seulement sur les entiers naturels mais aussi sur les parties de ℕ. Je dirai qu'un énoncé est Δ¹₀ s'il est Π_n (=Π⁰_n) ou Σ_n (=Σ⁰_n) pour un certain n ; je dirai qu'un énoncé est Σ¹₁ s'il s'obtient à partir d'un énoncé Δ¹₀ (resp. Π¹₀) par ajout d'un quantificateur existentiel (resp. universel) portant sur les parties de ℕ (ou sur les nombres réels, ou sur les suites d'entiers, ça revient au même). On aura deviné ce qu'est un énoncé Σ¹_n ou Π¹_n en général : quelqu'un qui croît que de tels énoncés sont vrais ou faux sera dit (1,n+1)-platonicien. Tous ces énoncés s'appellent énoncés arithmétiques du second ordre (par opposition à ceux qui n'avaient que des quantifications sur les entiers naturels et qui sont dits arithmétiques du premier ordre).

Exemple d'énoncé mathématique Π¹₃ : si B est un borélien de ℝ, alors le jeu à deux joueurs où chaque joueur choisit tour à tour une décimale d'un réel, et où (au bout d'un temps infini) le premier joueur gagne si le réel ainsi formé appartient à B et l'autre joueur s'il n'y appartient pas, [ce jeu] admet forcément une stratégie gagnante pour un des deux joueurs. (Il s'agit du théorème de détermination borélienne : c'est un théorème de ZFC, par ailleurs difficile. La raison pour laquelle c'est bien un énoncé Π¹₃ c'est qu'on peut coder les boréliens de ℝ comme des suites d'entiers, ainsi que les stratégies gagnantes, ou la suite des coups joués par un des deux joueurs.) Si on remplace borélien par analytique (i.e., image d'un ensemble borélien par une fonction continue, ce qui peut toujours se coder avec des suites d'entiers), alors l'énoncé résulte d'hypothèses de grands cardinaux qui dépassent ZFC (l'existence de x^♯ pour tout réel x). Un (1,4)-platonicien devra penser que cet énoncé est soit vrai soit faux : pour ma part, je commence à être sceptique sur le fait que ça ait vraiment un sens.

Le problème avec les parties de ℕ, c'est qu'on ne sait pas exactement ce qu'elles sont, on ne peut pas les déterminer complètement comme un entier naturel. (Kronecker : Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.) Je peux certes imaginer de reprendre mon jeu à deux joueur (Forall et Exists) et imaginer que ces joueurs échangent non plus des entiers naturels mais des Oracles qui permettent de savoir si un entier naturel est ou n'est pas dans la partie en question, mais je trouve que ça devient philosophiquement fumeux dans la mesure où chacun doit avoir le droit de poser un nombre infini de questions à n'importe quel Oracle choisi antérieurement, et de se décider en fonction de ça. Or peut-être qu'il y a dans l'univers une certaine limitation sur ce qu'un Oracle peut dire ou sur la façon dont on peut l'interroger, et cette limitation va affecter la notion de vérité pour les énoncés d'ordre supérieur.

En fait, voici un énoncé Σ¹₁, qui est un théorème de ZFC, et qui commence déjà à montrer la subtilité : il existe une partie de ℕ qui code la vérité des énoncés arithmétiques du premier ordre (tel quel ce n'est pas un énoncé mathématique correctement formalisé, mais il le devient si on le code comme ceci : il existe une partie de qui contient les codes de tous les énoncés Δ₀ vrais [ça ça ne pose pas de problème à définir, il y a même une définition Δ₁ uniforme] et aucun code d'un énoncé Δ₀ faux, et elle contient le code d'un énoncé pour tout x <machin> ssi elle contient le code de <machin> avec n remplacé pour x, pour tout n, et pareil pour il existe). On voit qu'admettre la vérité d'un tel énoncé c'est non seulement admettre qu'un énoncé arithmétique du premier ordre a toujours une valeur de vérité bien définie, mais aussi qu'on puisse s'en servir pour former une partie de ℕ : comme la verité des énoncés arithmétiques du premier ordre n'est certainement pas définissable par un prédicat arithmétique du premier ordre (il n'existe pas de prédicat P arithmétique du premier ordre tel que P(‹Q›) ⇒ Q dès que ‹Q› est le code d'un énoncé Q arithmétique du premier ordre), admettre l'existence d'une telle partie c'est déjà dépasser substantiellement ce que permet l'arithmétique du premier ordre. Maintenant, dans ZFC c'est un théorème (à peu près évident), mais il y a des théories suffisantes pour faire à peu près toutes les maths envisageables et dans lesquelles un tel énoncé est inaccessible. Bref, si je suis (1,0)-platonicien (ce qui est pareil que (1,1), en fait, avec ma convention), je ne suis pas certain d'être (1,2)-platonicien.

Évidemment, on peut aller au-delà et admettre des quantifications sur les parties de parties de ℕ (i.e., les parties de ℝ). Un énoncé Σ²₁ admet un quantificateur existentiel portant sur les parties de parties de ℕ devant n'importel quel énoncé Π¹_n (pour un n quelconque). L'hypothèse du continu, par exemple, est un énoncé Π²₂. Pour ma part, je ne pense pas que ça ait beaucoup de sens de se demander si elle est vraie ou fausse : je pense que c'est plus une question de convention sur ce qu'on veut admettre comme ensembles. (Et on est généralement d'accord que pour les ensembles les plus sympathiques et/ou naturels, l'hypothèse du continu est violemment fausse.) Enfin, il y a des énoncés de ZFC qui ne se laissent pas réécrire comme des énoncés de l'arithmétique d'ordre supérieur (ce que j'ai défini) : par exemple, il existe un cardinal inaccessible ne peut pas se décrire[#] comme Σ^r_n pour aucun r et n.

En revanche, ce qu'il faut souligner, c'est que même s'il faut un niveau de platonisme très élevé pour accepter de discuter de la vérité ou non de il existe un cardinal inaccessible et autres notions exotiques de la théorie des ensembles, en revanche, l'idée qu'un cardinal inaccessible puisse exister, c'est-à-dire soit consistante avec ZFC, ça c'est quelque chose de purement arithmétique, c'est même un énoncé simplement Π⁰₁. Et je suis pour ma part persuadé que c'est vrai : c'est là, d'ailleurs, que ma position philosophique se casse la gueule, parce que si je suis prêt à admettre qu'un cardinal inaccessible puisse exister mais pas que ça ait un sens de se demander s'il existe, on se demande un peu d'où je tire la conviction qu'il puisse exister (ce n'est pas un théorème de ZFC si ZFC est consistant, donc la croyance en une telle chose ne peut venir que d'une idée de grands cardinaux, quelque part). Du coup je ne sais pas bien ce que je crois.

En fait, j'ai l'impression que les théoriciens des ensembles sont souvent beaucoup plus platoniciens que les autres mathématiciens (ils avouent souvent publiquement être persuadés que l'hypothèse du continu est fausse, qu'un cardinal mesurable ou supercompact existe, etc.). Je pense que c'est lié au fait que les autres matheux peuvent tout à fait travailler sans avoir besoin de considérer de tels énoncés, alors que si on veut faire de la théorie des ensembles il est un peu malheureux de se dire qu'on ne manipule que des symboles qui ne veulent rien dire… Peut-être que les théoriciens des ensembles ont accès à un paradis platonicien plus vaste que le reste des matheux ? (Hilbert : Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können.)

[#] Ça c'est dans la hiérarchie arithmétique (d'ordre supérieur), que j'ai décrite, bien sûr : parce que comme énoncé ensembliste, il existe un cardinal inaccessible est quelque chose comme Σ₂.

Commentaires

2008-04-16 (mercredi)

L'astéroïde et les journalistes

Attention, je vais faire mon David Monniaux (ce dernier est actuellement en déplacement, donc je prends le relai pour la dénonciation des c***eries des journalistes ).

On a pu voir passer ce matin la dépêche suivante :

2008-04-16T09:19+0200 — Berlin — AFP

Un Allemand de 13 ans a corrigé des calculs de la NASA sur la probabilité de collision d'un astéroïde avec la Terre et l'Agence a reconnu son erreur.

À partir d'observations télescopiques à l'Institut d'astrophysique de Potsdam (AIP), près de Berlin, le lycéen Nico Marquardt a calculé une probabilité de 1 sur 450 qu'un astéroïde baptisé Apophis entre en collision avec la Terre, a rapporté le quotidien régional Potsdamer Neuerster Nachrichten.

La NASA, qui avait estimé à 1 sur 45.000 la probabilité d'un tel impact, a fait savoir — via l'Agence européenne de l'espace (ESA) — que le jeune génie avait raison.

Le facteur intégré par Nico Marquardt que l'Agence américaine n'avait pas pris en compte est le danger de collision d'Apophis avec l'un ou plusieurs des 40.000 satellites lors du passage près de la planète bleue le 13 avril 2029.

Ces satellites tournent à une vitesse de 3,07 km/seconde autour de la Terre à une distance allant jusqu'à 35.880 kilomètres: or l'astéroïde devrait passer à 32.500 kilomètres de notre planète. Si un impact a lieu en 2029, cela pourrait changer la trajectoire d'Apophis de manière à lui faire rencontrer notre planète lors de son prochain passage près de la Terre prévu en 2036.

La NASA et Nico Marquardt estiment qu'en cas de collision, la boule de fer et d'iridium d'un diamètre de 320 mètres et lourd de 200 milliards de tonnes tomberait dans l'Océan Atlantique. Ce choc déclencherait des vagues monstrueuses, ravageant les côtes et bien au-delà, tandis que des masses extrêmement denses de poussière dans l'atmosphère assombriraient le ciel pour un temps indéterminé.

Nico Marquardt avait fait connaître sa découverte dans le cadre d'un concours régional qu'il avait remporté grâce à son travail intitulé L'astéroïde meurtrier Apophis.

Le problème ? Le problème, c'est que tout est faux là-dedans, ou presque. Petit jeu : relisez calmement et rendez-vous compte que, même sans avoir accès à des données extérieures, on doit avoir la puce à l'oreille.

Commençons par le plus énorme : je ne sais pas comment le chiffre de 200 milliards de tonnes a pu arriver dans ce texte, mais n'importe qui capable de calculer le volume d'une boule, ce qui est au programme de la classe de Troisième, peut calculer celui d'une boule de 320 mètres de diamètre (ce qui fait : dans les 17 millions de mètres cubes) donc la densité de l'astéroïde si on en croit cette dépêche (200 milliards de tonnes divisé par 17 millions de mètres cubes égale : plus de 11000 tonnes par mètre cube, ou encore 11 tonnes par litre). Comment quelqu'un peut-il avoir un sens des ordres de grandeurs à ce point absent pour ne pas s'apercevoir que c'est idiot ? Si encore on imaginait que la boule était formée de je ne sais quelle matière bizarre (les naines blanches ou les étoiles à neutron ont des densités très élevées, c'est vrai), ce serait juste une question d'ignorance, mais, là, c'est écrit : fer et iridium !

Soit on doit supposer que notre journaliste n'a jamais fait sa troisième, et en tout cas qu'il ne sait pas calculer le volume d'une boule, soit il s'imagine que le fer pèse plusieurs tonnes le litre, soit, ce qui est plus vraisemblable, il avale tout ce qu'on lui dit sans réfléchir une seule seconde (jusqu'où aurait-il été crédule ? si on lui avait parlé d'un astéroïde de 20000km de diamètre, aurait-il marché ? j'ai peur que oui…).

Par ailleurs, il se trouve que les données rapportées sur cet astéroïde 99942 Apophis sont tous faux : la meilleure estimation de son diamètre est un chouïa plus petite que les 320m indiqués par le journaliste, autour de 270m, et cette classe d'astéroïdes (les chondrites) est plutôt pauvre en métaux m'apprend un ami planétologue. Là il s'agit d'erreurs mineures, certes, mais il aurait suffi de taper le nom de l'astre dans un moteur de recherche pour trouver ces données précises ainsi qu'une estimation de la densité des astéroïdes typiques : on se rend compte que la valeur plausible de la masse est autour de 21 millions de tonnes (confirmation ici), pas 200 milliards ! Évidemment, la Wikipédia donnait les valeurs correctes, mais les journalistes français aiment bien se moquer de l'inexactitude de Wikipédia (l'AFP interdit de l'utiliser comme source), eux qui, hu hu hu, savent tellement mieux.

Passons sur l'erreur de niveau troisième et regardons maintenant le fond de l'histoire. Est-il vraiment raisonnable de penser que l'agence spatiale américaine ne serait pas au courant de l'existence de satellites géostationnaires ? Bien sûr que non — je ne comprends pas comment un journaliste a pu une seconde croire une telle chose. La vérité, c'est que ces satellites n'ont pas à être pris en compte : certes, l'astéroïde va passer plus près de la Terre que la distance des satellites en question, mais les satellites géostationnaires sont dans le plan de l'équateur et l'orbite de l'astéroïde traversera le plan de l'équateur plus loin que les satellites géostationnaires ; là aussi, il suffisait de chercher un peu sur le Web pour le savoir : because Apophis will pass interior to the positions of these satellites at closest approach, in a plane inclined at 40 degrees to the Earth's equator and passing outside the equatorial geosynchronous zone when crossing the equatorial plane, it does not threaten the satellites in that heavily populated region. Par ailleurs, même en prenant la valeur vraie de la masse de l'astéroïde (de l'ordre de 20 millions de tonnes, donc) et à plus forte raison si on prend la valeur imaginée par le journaliste (200 milliards), en imaginant la collision d'un tel truc contre un satellite qui pèse au grand maximum quelques tonnes, je veux bien que ça perturbe l'orbite, mais ça va la perturber de l'ordre d'une fraction de partie par million, ce qui n'est pas considérablement plus que les erreurs de mesure qu'on peut imaginer sur ce genre de situation, donc faire passer la probabilité de 1 sur 45000 à 1 sur 450, c'est assez louche. On ne peut peut-être pas s'attendre à ce que le journaliste bronche à ça, mais la multiplication de la probabilité par exactement 100 ça devrait au moins éveiller des soupçons sur ce chiffre.

Je passe aussi sur le fait que l'observatoire radio de l'institut d'astrophysique de Potsdam ne semble pas faire d'astronomie radar (en tout cas ils ne la mentionnent pas) : pour autant que je sache, les données qu'on a sur 99942 Apophis viennent du radar planétaire d'Arecibo. Ça c'est pour dire qu'il ne pouvait pas vraiment y avoir de nouvelles données expérimentales que la NASA n'aurait pas prises en compte.

Mais le plus énorme, finalement, c'est cette histoire selon laquelle la NASA aurait confirmé son erreur (via l'ESA, ce qui est une autre bizarrerie, mais on n'est plus à ça près). Vous croyez que le journaliste aurait pris la peine de vérifier, d'aller voir s'il y avait une quelconque note officielle dans ce sens ? Non, évidemment. Même le site pourtant pas très reconnu pour sa fiabilité qu'est The Register a été foutu, lui, de demander confirmation : résultat, non, l'ESA nie tout. On atteint des limites invraisemblables dans le ridicule.

Si vous voulez mon explication de ce qui a pu se passer, ma boule de cristal suggère que le jeune Allemand aurait fait un calcul rapide et sans doute pas complètement idiot de ce qui pourrait se passer — i.e. de l'ordre de grandeur de l'erreur — en cas de collision avec un satellite, il se serait aperçu que ça apportait un terme d'erreur supplémentaire pas pris en compte, mais il n'aurait pas été au courant que cette collision n'était pas possible (ou il n'aurait pas eu les éléments orbitaux corrects) et il n'aurait pas su non plus que la principale cause d'incertitude est en fait l'inexactitude des théories planétaires. Il aurait ensuite écrit un petit papier là-dessus, un journal régional aurait repris la nouvelle sans trop chercher à en savoir plus. Un journaliste censément d'envergure plus internationale aurait vu ça et aurait appelé quelqu'un à l'ESA sans chercher à trouver le bon interlocuteur : il serait tombé sur quelqu'un qui aurait pris en vitesse des vieilles données sur 99942 Apophis et aurait dit ah oui, effectivement, la probabilité de collision est quelque chose comme 1/450 (parce qu'on a effectivement cru à une probabilité de l'ordre du pour cent par le passé). Le journaliste aurait pris ça comme un aveu d'erreur et aurait diffusé l'information surtout sans rien vérifier de plus.

C'est absolument pathétique, surtout que maintenant tout le Web en parle et j'imagine que l'« info » va se retrouver dans un certain nombre de journaux réputés fiables. Ça donne une idée de comment ces gens font leur travail… tout de même, une probabilité de 1/450 de catastrophe assez importante en 2037, ça méritait une certaine attention, pas d'être pris complètement par-dessus la jambe. Mais j'imagine que le sensationnalisme du prétendu génie qui ferait des calculs mieux que la NASA (vraiment une idée conne de type qui a regardé trop de nanars, ça), ça passait avant la vérification de ses sources.

Je ne sais pas dans quelle mesure ce phénomène est limité aux articles de science (i.e., dès qu'on écrit sur de la science, on ferme son cerveau parce que c'est compliqué, la science, n'est-ce pas), et malheureusement il n'y a que dans ce domaine que je puisse nettement repérer les erreurs, mais ce que racontait David Monniaux récemment ou encore plus récemment donne peu confiance. Personnellement je prends mes nouvelles du monde par la BBC, qui n'est certes pas parfaite mais elle a un chouïa moins tendance à raconter des c***eries à sensation quand il s'agit de science.

Précision : Je suis bien conscient qu'il ne s'agit « que » d'une dépêche de l'AFP, et que les journalistes des quotidiens qui reçoivent ces nouvelles sont censés faire une démarche de vérification ou d'éclaircissement de leur part. Apparemment cette fois-ci ça a marché puisque par exemple Libération a remarqué l'erreur. J'imagine que l'affaire était suffisamment grosse pour qu'on se renseigne un peu, et les démentis étaient faciles à trouver (comme justement on en a beaucoup parlé, ils sont arrivés vite). Reste qu'émettre une dépêche de ce genre sans faire un calcul de niveau troisième est inexcusable.

Commentaires

2008-04-10 (jeudi)

Qu'est-ce qu'un nombre aléatoire ?

Voici une question un peu provocante : qu'est-ce qu'un nombre aléatoire ? Pour un probabiliste, elle n'a pas de sens : un nombre n'est pas aléatoire (le nombre π, par exemple, ça n'a pas de sens de dire qu'il est aléatoire), ce qui a un sens, c'est de tirer aléatoirement un nombre, disons, dans l'intervalle [0;1]. Pourtant, il y des branches des mathématiques où cela a bien un sens, de façon abolue, de dire qu'un nombre réel bien défini est — ou n'est pas — aléatoire (et, pour gâcher le suspens, le nombre π n'est pas aléatoire, en aucun sens qu'on sache définir à ma connaissance, ce qui est bien dommage parce que ça permettrait de prouver plein de choses merveilleuses à son sujet, mais c'est tout à fait intuitif parce qu'on arrive à le calculer — donc il n'est certainement pas tiré au hasard !). Je vais tâcher d'expliquer simplement de quoi il retourne, sans entrer dans trop de technicité mais en donnant tout de même des définitions complètes. L'idée qu'on cherche à développer est que :

L'aléatoire est ce qu'on ne peut prévoir (de façon non triviale) par le calcul.

Plutôt que de travailler sur des nombres réels, je travaillerai sur des suites infinies de 0 et de 1, ce qui est presque pareil (comme aucun rationnel dyadique, ou aucun rationnel tout court, d'ailleurs, n'est aléatoire en aucun sens, on peut considérer qu'une suite infinie de 0 et de 1 est la même chose que le nombre réel entre 0 et 1 qui a cette écriture binaire). Appelons Ξ (j'allais l'appeler 𝔠, mais je pense que si je fais ça beaucoup de gens ne vont rien voir d'utile) l'ensemble des suites infinies de 0 et de 1. On aura besoin de la notion d'ouvert de Ξ: un ensemble U de suites est dit ouvert lorsque c'est une réunion d'ensembles de la forme toutes les suites commençant par <un nombre fini de symboles> ; ou, de façon équivalente, lorsque pour toute suite de U il existe un rang à partir duquel on peut modifier n'importe comment la suite et rester dans U. Autrement dit, l'ensemble de toutes les suites commençant par 0, ou par 01101001, ou par 11111111, sont des ouverts, ainsi que n'importe quelle réunion — même infinie — de telles choses (par exemple, l'ensemble des suites commençant par 0 ou 11 ou 100 ou 1011 ou…), et ce sont là tous les ouverts de Ξ. (La notion d'ouvert de Ξ ne coïncide pas avec la notion plus habituelle d'ouvert de [0;1], par exemple parce que Ξ n'est pas connexe, mais la différence n'est pas importante pour ce que je vais dire.)

On dira qu'un ouvert (ou, d'ailleurs, n'importe quel ensemble) est dense lorsque son complémentaire (i.e., l'ensemble des suites qui ne sont pas dedans) ne contient aucun ouvert autre que ∅ (le vide, qui est un ouvert). Voici un exemple d'ouvert dense : l'ensemble de toutes les suites sauf la suite 000000… (ou sauf n'importe quelle suite donnée, d'ailleurs) : il est facile de vérifier que c'est un ouvert (c'est l'ensemble des suites commençant par 1, ou par 01, ou par 001, ou par 0001, autc.), et il est encore plus facile de se convaincre que son complémentaire (qui ne contient qu'une seule suite, la suite nulle) ne contient aucun ouvert non vide. L'idée est qu'un ouvert dense contient « quasiment toutes » les suites ; mais ça, ça va servir à définir les suites génériques, qui ne sont pas pareilles que les suites aléatoires.

Pour définir ce que c'est qu'une suite aléatoire j'ai besoin d'une autre notion, celle de mesure d'un ouvert (moralement, la probabilité qu'une suite de 0 et de 1 tirés au hasard indépendamment avec probabilité ½ pour chacun, tombe dans l'ouvert). J'ai dit qu'un ouvert pouvait s'écrire comme une réunion de machins qui sont toutes les suites commençant par <bla bla bla>, où <bla bla bla> ne comporte qu'un nombre fini de 0 et de 1 (on appelle de tels machins des ouverts élémentaires) : avec un petit peu d'efforts on peut s'arranger pour que la réunion soit disjointe (il suffit de retirer ce qui est redondant dans la description : l'ensemble des suites commençant par 0 ou 01, c'est juste l'ensemble des suites commençant par 0). On attribue à chacun de ces ouverts élémentaires une mesure qui est ½ⁿ (un demi puissance n) avec n le nombre de symboles imposés au début, et on ajoute toutes ces mesures pour calculer la mesure de la réunion disjointe. Par exemple, l'ouvert des suites commençant soit par 0 soit par 111, a pour mesure 5/8 (= 1/2 + 1/8) ; l'ensemble des suites autres que la suite 000000… (j'ai expliqué plus haut que c'était un ouvert) a pour mesure 1, comme l'ensemble Ξ de toutes les suites : un tel ouvert est dit de mesure pleine. Il s'avère qu'un ouvert de mesure pleine est forcément dense (pourquoi ?), mais la réciproque n'est pas vraie — si ça ne vous saute pas aux yeux, c'est sans doute normal, mais ça vaut le coup d'y réfléchir.

J'en viens à la notion de suite aléatoire et de suite générique. Mais avant ça j'aurai besoin d'une notion de calculabilité ; pourtant, je ne vais pas définir ce que c'est : ce qui est intéressant, c'est que pour chaque notion de calculabilité, je vais avoir une notion de suite aléatoire et de suite générique, qui sera d'autant plus contraignante que la notion de calculabilité est puissante. La notion la plus naturelle, c'est la calculabilité habituelle de Church-Turing (les fonctions récursives, qui sont en gros celles que peut calculer un ordinateur idéalisé), mais plein d'autres notions pourraient convenir : soit plus fortes (fonctions récursives sous un oracle quelconque, fonctions Σ_n de l'arithmétique, fonctions arithmétiques, fonctions hyperarithmétiques, fonctions analytiques-au-sens-de-la-calculabilité, fonctions constructibles-au-sens-de-l'univers-de-Gödel), soit plus faibles (fonctions primitives récursives, et sans doute même fonctions calculables en temps polynomial même si quand la calculabilité devient trop faible j'ai peur que les notions que je vais définir ne soient plus très bonnes).

Le but de ces fonctions calculables sera juste de pouvoir dire que certains ouverts de Ξ sont calculables : un ouvert calculable U sera juste un ouvert tel qu'une fonction calculable (donc un programme informatique idéalisé, si vous prenez la calculabilité au sens de Church-Turing) qui quand on lui présente un mot fini de 0 et de 1 décide si l'ouvert élémentaire des suites commençant par ce préfixe sera mis dans la réunion constituant U. Autrement dit, on lui demande veux-tu mettre dans l'ouvert toutes les suites commençant par 0 ?, veux-tu mettre dans l'ouvert toutes les suites commençant par 1 ?, veux-tu mettre dans l'ouvert toutes les suites commençant par 00 ?, etc., et elle prend à chaque fois une décision[#]. À titre d'exemple, tant que votre notion de calculabilité n'est pas démesurément faible, l'ensemble des suites qui ne sont pas la suite nulle — ensemble dont j'ai déjà dit que c'était un ouvert par ailleurs dense et de mesure pleine — est calculable, puisque c'est très facile de reconnaître les mots 1, 01, 001 et de répondre oui sur chacun d'entre eux. On peut aussi demander qu'une suite d'ouverts soit calculable : cela signifie que la fonction calculable prend en outre en entrée un entier (n) qui est le rang dans la suite. On définit enfin une suite décroissante calculable d'ouverts de Ξ : cela signifie simplement que la suite est décroissante pour l'inclusion (i.e., chaque ouvert est inclus dans tous les précédents), ou, si on préfère, quand la fonction calculable a décidé d'exclure un ouvert élémentaire d'un terme de la suite, elle exclut automatiquement de tous les suivants.

Quel est maintenant l'esprit de la définition ? Une suite aléatoire/générique est, en gros, une suite sur laquelle on ne puisse pas faire une prévision calculatoire non-triviale. Évidemment, on pourra toujours dire elle commence par 010100 (disons), puisque c'est une suite bien définie (je rappelle que je suis en train de définir une notion d'aléatoire qui s'applique pour une suite bien définie !) ; mais l'idée est qu'on ne peut pas faire une prévision vraiment intéressante.

Voici enfin les deux notions en question :

Une suite est dite générique lorsqu'elle appartient à tout ouvert dense calculable.

Une suite x est dite aléatoire lorsque pour toute suite décroissante calculable (U_n) d'ouverts de Ξ telle que le n-ième soit de mesure au plus 1/n, la suite x n'appartient qu'à un nombre fini d'entre eux.

La définition d'une suite générique est sans doute plus simple à comprendre : si vous arrivez à faire une prévision calculable du type la suite n'est pas dans l'ouvert U que voici, alors cet ouvert ne peut pas être dense, c'est-à-dire qu'il y a quelque part un gros bout (toutes les suites commençant par un certain préfixe) qu'on a omis dans la prévision — qui n'a donc rien de remarquable (je peux bien faire la prévision la suite commence par 0101010, et il y a bien certaines suites aléatoires qui vont y coller). Dit autrement, un ouvert dense calculable contient toutes les suites génériques. Donc j'ai déjà prouvé que la suite 000000… n'est pas générique : il existe un ouvert dense (toutes les suites sauf elle !) qui est calculable et qui ne la contient pas.

La définition d'une suite aléatoire est un chouïa plus compliquée, parce que cette fois-ci on demande de faire des prévisions du type la suite est dans l'ouvert U que voici ; or on peut certainement faire des prévisions de ce style (de nouveau, je peux faire la prévision la suite commence par 0101010, et il y a bien certaines suites aléatoires qui vont y coller), on peut même certainement faire des prévisions aussi bonnes qu'on veut, mais le point important est qu'on ne peut pas le faire uniformément : si on a une suite décroissante calculable d'ouverts dont le n-ième a une mesure au plus 1/n[#2], son intersection ne contient aucune suite aléatoire. Ceci étant, on se convainc facilement que, par exemple, la suite nulle 000000… n'est pas aléatoire (de nouveau, dès que la notion de calculabilité n'est pas démesurément faible) : il suffit de considérer la suite décroissante d'ouverts donnée par les suites dont les n premiers termes sont nuls — cela donne une mesure de 1/2ⁿ.

J'ai donc prouvé que la suite nulle n'était ni aléatoire ni générique. C'est la moindre des choses. En fait, pour la même raison, n'importe quelle suite calculable au sens qu'on s'est fixé n'est ni aléatoire ni générique. En revanche, si je prends une suite aléatoire (resp. générique) et que je remplace un sur deux de ses chiffres par un 0, j'obtiens une suite qui n'est plus aléatoire (resp. générique) et qui n'est pourtant pas calculable : donc aléatoire et génériques ne sont pas synonymes de pas calculables — ils sont bien plus forts que ça.

Le fait qu'il existe des suites aléatoires et des suites génériques résulte, si la notion de calculabilité est dénombrable (i.e., s'il n'existe qu'une infinité dénombrable de fonctions calculables ℕ→ℕ, ce qui est le cas pour la calculabilité au sens de Church-Turing), résulte du théorème de Baire dans un cas (l'intersection de tous les ouverts denses calculables est non vide) et de l'additivité de la mesure dans l'autre (la réunion de toutes les intersections de suites décroissantes calculables d'ouverts dont la mesure tend vers zéro est de mesure nulle). Pour d'autres notions, cela peut être plus difficile ou impossible (si on déclare que toutes les fonctions ℕ→ℕ sont calculables, il n'y a plus aucun nombre aléatoire ou générique : pour un être omniscient, il n'y a pas de hasard).

Voici maintenant un résultat que j'ai toujours trouvé remarquable : on s'imagine que générique et aléatoire veulent tous les deux dire, de manière vague qu'on ne peut pas calculer de prévision aléatoire non triviale dessus ; pourtant, pour toute notion (un tant soit peu raisonnable) de calculabilité,

Aucune suite n'est simultanément générique et aléatoire.

La démonstration n'est pas compliquée ! Considérons, pour chaque n, l'ouvert U_n de Ξ ainsi défini : il s'agit de l'ensemble des suites de 0 et de 1 qui commencent par k signes quelconques (pour un certain k fini) qui sont immédiatement suivis de 2k+n fois 0 (et ensuite n'importe quoi) : cette description montre immédiatement qu'il s'agit d'un ouvert, il est assez clair qu'il est calculable (il est très facile de reconnaître les mots formés de k signes quelconques puis 2k+n fois 0), et même, que la suite (U_n) d'ouverts de Ξ est décroissante calculable. Maintenant, chacun des ouverts U_n est dense (car vous aurez beau prescrire comme vous voudrez les N premiers termes d'une suite, vous n'éviterez jamais à qu'elle puisse être dans U_n), et pourtant sa mesure est majorée par 1/2ⁿ ou quelque chose de ce goût-là (c'est une réponse à la question que j'avais posée plus haut : montrer qu'il existe des ouverts denses qui ne sont pas de mesure pleine). Du coup, une suite générique doit appartenir à chacun des U_n, alors qu'une suite aléatoire ne peut appartenir qu'à un nombre fini d'entre eux. Cela empêche qu'une suite aléatoire soit générique.

Ce résultat est difficile à comprendre intuitivement : je pense que les suites génériques sont plus élusives que les suites aléatoires — elles donnent l'impression d'avoir des motifs dedans, ce qui est faux, bien sûr, mais elles ne se comportent pas du tout comme les suites aléatoires. Philosophiquement parlant, la suite de 0 et de 1 qu'on obtiendrait en tirant infiniment à pile ou face est assurément aléatoire, mais je ne sais pas d'où on pourrait sortir une suite générique : notre monde a l'air beaucoup plus naturellement orienté vers l'aléatoire que vers le générique[#3] — pourtant, mathématiquement, il existe une grande similarité entre ces deux notions (voir à ce sujet le livre d'Oxtoby fort justement intitulé Measure and Category).

Les suites (ou nombres réels) aléatoires et surtout génériques ont une grande importance en théorie des ensembles : par exemple, la façon dont Paul Cohen a montré l'indémontrabilité de l'hypothèse du continu c'est de fabriquer (par la technique du forcing) énormément de suites de 0 et de 1 (ou nombres réels) qui soient génériques (en fait, aléatoire marcherait aussi) en prenant pour notion de calculabilité la constructibilité au sens de l'univers de Gödel, qui est à peu près la plus forte qu'on puisse imaginer (très très grossièrement, c'est la puissance qu'aurait en quelque sorte un ordinateur capable de calculer directement sur les ensembles et sur des temps transfinis). À l'autre bout du spectre de la calculablité, on pourrait placer la cryptographie, où la notion d'oracle aléatoire sert de modèle pour des preuves de sécurité de cryptosystèmes et où on est bien forcé de constater que ce n'est pas une notion si atteignable. Je me demande s'il y aurait lieu de considérer des oracles génériques (le terme a été utilisé, mais je crois que c'est pour quelque chose se très différent).

[#] Pour la calculabilité au sens de Church-Turing, on peut prendre l'absence de réponse, i.e., la non-terminaison du programme, comme une réponse négative, ou bien l'interdire, ça ne changera rien à la notion d'ouvert calculable.

[#2] Ça fait partie des choix pas forcément évidents à faire quand on prend une notion de calculabilité trop faible… déjà, pour la calculabilité au sens de Church-Turing, il faut se convaincre que le bon choix est bien d'imposer explicitement une vitesse de convergence et pas juste de dire la mesure de U_n tend vers 0 : un des critères qui me poussent à faire ce choix, c'est que, si je ne me trompe pas, il permet alors avec l'oracle de l'arrêt des machines de Turing de construire un réel aléatoire (de même qu'on peut en construire un générique), ce qui ne serait pas possible si on demandait juste que la mesure tende vers zéro. Mais je ne suis pas totalement sûr de moi, et je le suis encore moins pour des notions de calculabilité très faibles comme la calculabilité en temps polynomial (où ça fait une différence de demander que la mesure soit bornée par 1/n ou 1/2ⁿ), et même pour la calculabilité de Church-Turing il faudrait calibrer les choses par rapport à une autre définition habituelle (mais à mon avis moins agréable) qui fait intervenir la complexité de Kolmogorov. Enfin bon, l'esprit est quand même raisonnable dans tous les cas, et pour les notions de calculabilité assez fortes (du genre être arithmétique), ça ne fait pas de différence.

[#3] Voici un autre fait digne d'intérêt : un nombre réel générique est un nombre de Liouville, c'est-à-dire qu'il s'approche très bien par les nombres rationnels, alors qu'un nombre réel aléatoire est approché par les rationnels exactement à l'ordre 2 (c'est-à-dire qu'il est à une distance d'un rationnel de l'ordre de la puissance −2 du dénominateur de celui-ci) ; or il se trouve que les nombres qui interviennent « naturellement » en analyse, en tout cas le nombre e, sont ou ont l'air d'être, approchés exactement à l'ordre 2. Du coup, en un sens qui semble malheureusement impossible à rendre précis, les décimales de e ou π sont plus proches d'être aléatoires que génériques (en vérité, elles ne sont ni l'un ni l'autre : il faudrait une notion furieusement faible de calculabilité pour que π soit aléatoire !).

Commentaires

2008-04-06 (dimanche)

Affres scientifiques

Mes intérêts, scientifiques notamment, ont tendance à suivre une marche aléatoire dirigée par un certain nombre d'attracteurs assez chaotiques. Récemment j'ai eu le malheur de tomber sur des questions de logique / théorie des ensembles, et ces questions tout particulièrement sont comme les têtes de l'hydre : quand on en coupe une (en la résolvant), il y en a un nombre indéfini de nouvelles qui poussent. Et le pire c'est que ces questions ont l'air tellement simples (pour qui connaît le domaine…) et séduisantes qu'elles me prennent d'une frénésie qui fait que j'ai vraiment du mal à penser à autre chose.

Il va bien falloir, pourtant, que je pense un peu à autre chose, ne serait-ce que parce que j'ai d'autres choses à faire !: un cours (d'optimisation) qui commence après-demain, d'autres projets mathématiques commencés, etc. Mais je n'aime pas laisser une hydre sans avoir coupé toutes ses têtes.

Sinon, j'ai appris que j'ai reçu l'appellation définitive de maître de conférences (j'étais recruté sur une appellation provisoire). Et aussi, mes transparents de mardi ont été acceptées par le Journal of Craptology, mais je pense que je vais éviter de trop revendiquer cette information ou de la faire figurer sur mes CV.

Commentaires

2008-04-01 (mardi)

Fourtytwofish

Ceux qui n'ont pas pu assister à ma brillante présentation tout à l'heure peuvent néanmoins en consulter les transparents. Enjoy!

Commentaires

2008-04-01 (mardi)

Séparation

Jean-Gustave et moi avons finalement décidé de nous séparer : c'est ainsi que je révèle le nom de celui que je ne voulais qu'appeler mon copain en même temps qu'il ne l'est plus. Précisons que c'est d'un accord commun que nous mettons un terme à notre relation : nous avons échangé plusieurs SMS pour négocier les conditions de cette rupture, et nous restons en très bons termes (d'ailleurs son avocat vient de m'annoncer qu'il me laissait 48h de rallonge pour évacuer l'appartement). Cela valait sans doute mieux : j'avoue ne jamais avoir réussi à bien partager sa passion pour la philatélie et pour Claude François, tandis que pour sa part il n'a pas pu dépasser sa phobie des ordinateurs.

Bref, une page se tourne. J'ai voulu l'annoncer ici sobrement.

Commentaires