Illustration FlickR CC : Cayusa

—

[Liens en anglais, sauf mention contraire] Dans “Why are past, present, and future our only options?“, Dave Goldberg traite de la “question bête” d’un lecteur de son livre qui se demande à quoi ressemblerait l’univers si le temps avait plus d’une dimension, et plus généralement, si la vie serait imaginable dans un univers à N≠3 dimensions. Voici quelques idées qu’il y développe, additionnées des miennes sur ce sujet.

La vie dans un espace à 2 dimensions (+1 temps)  a été imaginée dès 1884 dans Flatland [fr], une allégorie purement géométrique dont a été tiré un film 2007 :

Cliquer ici pour voir la vidéo.

Un siècle plus tard, A.K. Dewdney a traité de manière beaucoup plus “scientifique” la physique, la chimie et la biologie dans le Planivers, répondant au passage à une objection de Dave Goldberg : oui, il est possible de croiser deux fils dans le Planivers, comme indiqué ici, donc de réaliser des ordinateurs en 2D, comme le montre également le ”Jeu de la Vie” [fr] qui est une machine “Turing complète” [fr].

Un univers à N=1 dimension (+1 temps) n’est pas imaginable en physique, mais du point de vue artistique j’aime beaucoup ”la Linea” de mon enfance, un dessin animé minimaliste en “1½ D” avec interventions ponctuelles d’un Créateur tridimensionnelle :

Cliquer ici pour voir la vidéo.

À propos d’un univers à N=4 dimensions spatiales [fr] (+1 temps toujours), Dave Goldberg mentionne un fait que je n’avais pas réalisé : l’action des forces n’y diminue pas comme l’inverse du carré de la distance comme dans notre univers, mais comme l’inverse du cube de la distance. Ceci fait notamment qu’aucune planète à 4 dimensions ne peut décrire une orbite stable autour de son soleil hypersphérique. Le problème ne s’arrangeant pas en augmentant les dimensions il faut se rendre à l’évidence : un univers “fertile”, où la complexité peut se développer jusqu’à permettre des formes de vie ne peut avoir que N=3 dimensions, ou à la rigueur 2.

Plus une seule dimension de temps, toujours. Quelle que soit la “nature du temps” [fr] on n’y coupe pas : au niveau macroscopique bien décrit par la relativité d’Albert, le temps est décrit par une dimension imaginaire [fr], au sens mathématique des nombres complexes. Évidemment, sans temps un univers serait désespérément statique et sans intérêt.

Mais peut-on imaginer un temps à plus d’une dimension ? Mathématiquement ça ne pose pas trop de problèmes et les caractéristiques de tels univers ont été étudiées, notamment par Max Tegmark. Son très intéressant article soulève la difficulté majeure posée par un univers à plusieurs dimensions de temps :

Si un observateur est capable d’utiliser sa conscience de soi et des capacités de traitement de l’information, les lois de la physique doivent être telles qu’il puisse faire au moins certaines prédictions. Plus précisément, au sein du cadre d’une théorie des champs, en mesurant diverses valeurs de champ à proximité, il faut qu’il ait la possibilité de calculer les valeurs de champ à certains points plus éloignés de l’espace-temps (ceux se trouvant le long de la ligne de son monde à venir sont particulièrement utiles) avec une marge d’erreur finie. Si ce type de causalité bien définie était absente, alors non seulement il n’y aurait aucune raison pour que cet observateur ait une conscience de soi, mais il semble très peu probable que des systèmes de traitement de l’information tels que les ordinateurs ou le cerveau puissent exister.

Or justement cette prédictibilité n’apparaît que si les équations de champ suivent des équations différentielles partielles “hyperboliques”. Et Tegmark montre que ceci n’est le cas que dans les univers à une seule dimension de temps ou une seule dimension d’espace. S’il y en a plus, l’univers devient totalement imprévisible. Avec un temps à deux dimensions, il est par exemple impossible de donner un rendez-vous à quelqu’un, car si nous contrôlons nos déplacements dans l’espace et pouvons éventuellement les moduler de façon à nous retrouver à un certain moment t1 selon le “temps1″ à l’endroit convenu, nous n’aurions pas le moyen de gérer simultanément le “temps2″ : l’autre personne suivant une trajectoire dans l’espace-temps différente n’aurait aucun moyen d’arriver au rendez-vous à la fois à la même position spatiale et au même temps (t1,t2)

Le tableau suivant résume les caractéristiques des univers selon leurs dimensions spatiales et temporelles selon Tegmark :

Notre univers n’est donc pas le résultat d’une expérience menée par des êtres à 4 dimensions, ou de dieux pour lesquels notre temps ne serait qu’une dimension parmi beaucoup d’autres. Nous ne sommes pas manipulés comme “La Linea”, ça soulage…

Le tableau exhibe aussi une jolie symétrie entre dimensions spatiales et dimensions temporelles, ce qui laisse espérer un autres univers intéressant, notre “symétrique” à une dimension spatiale et “temps cubique”. Dans cet univers, la physique des particules n’autorise que l’existence de tachyons [fr], des particules très hypothétiques dans notre univers mais liées à la théorie des cordes, laquelle postule l’existence de dimensions ”bouclées” à très petite échelle en plus des dimensions spatiales. Dès qu’on vérifie leur existence expérimentalement j’écris un article là-dessus, promis.

Turing l’informaticien

Ses contributions majeures sont dans le domaine de l’informatique. Turing est l’inventeur de l’ordinateur en tant qu’objet d’étude théorique. Il a ainsi littéralement défini le concept d’algorithme (et un concept qui va avec, la calculabilité). Dans le papier fondateur des sciences informatiques, il définit ce qu’on appelle aujourd’hui une machine de Turing. La machine de Turing est un dispositif théorique très simple, basé sur une machine lisant un ruban imprimé et, en fonction de ce qu’elle lit sur le ruban, pouvant avancer, reculer sur le ruban, écrire sur celui-ci ou effacer de l’information. On peut démontrer que tout ordinateur est en fait assimilable à une machine de Turing !

Ce qu’on sait moins, c’est que Turing a inventé sa machine (et donc l’ordinateur) pour répondre à un problème mathématique précis, posé par Hilbert dans sa fameuse liste. En fait, ses travaux font suite à ceux de Godel sur l’indécidabilité en mathématique. Turing pensait que le problème 10 de Hilbert était indécidable ; pour étudier ce genre de problème, son idée était en quelque sorte de “mécaniser”, d’automatiser les mathématiques, ce qui l’a amené à inventer la machine de Turing et la notion d’algorithme. Un des problèmes fameux qu’il a résolu avec sa démarche est le problème de l’arrêt. En terme “geek”, le problème de l’arrêt se formule en termes suivants : est-il possible de construire un algorithme capable de prédire si un programme informatique va imprimer les mots “hello world” ? Turing a posé le problème et montré qu’une telle machine, qu’un tel algorithme n’existait pas, et donc que le problème de l’arrêt est indécidable (la démonstration est assez facile à comprendre, je m’étais même fendu d’un petit billet à ce sujet à une époque lointaine …).

Les autres contributions d’Alan Turing

Turing était en fait fasciné par les machines, l’automatique, et se posait beaucoup de questions philosophiques sur la nature de la conscience et de l’intelligence. L’une de ses contributions majeures au domaine de l’intelligence artificielle est ce qu’on appelle le test de Turing : il s’agit, en gros, d’un test permettant de mesurer l’intelligence d’une machine à l’aune de l’intelligence humaine. Les fameuses CAPTCHA de nos blogs sont une forme de test de Turing. Ce cheminement des maths vers l’algorithmique en passant par la philosophie et l’intelligence artificielle ont amené Turing a s’intéresser à la formation de structures en biologie. Là aussi, il a cherché à savoir comment de la complexité pouvait émerger de processus purement mécaniques : il a ainsi proposé les premiers modèles mathématiques de réaction-diffusion, pour expliquer comment des motifs (de Turing) peuvent se former spontanément en biologie.

La plupart des travaux de Turing sont largement d’actualité dans toutes ces disciplines. La machine de Turing est le prototype théorique de l’ordinateur, l’intelligence artificielle est un domaine de recherche prometteur, et je suis très bien placé pour vous dire qu’on n’a pas fini d’entendre parler de Turing et de ses successeurs dans le domaine de la biologie théorique.

Turing, l’homme

Sur le plan plus personnel, la vie de Turing fut probablement assez triste et se termina très mal. Homosexuel, il perdit son premier amour foudroyé par la maladie (ce qui rendit Turing athée, comme Darwin), puis fut poursuivi et condamné dans un pays où les préférences sexuelles différentes étaient illégales. Du fait de sa condamnation, on lui interdit de poursuivre ses recherches sur la cryptographie. Désespéré, Turing se suicida en 1954 en mangeant une pomme empoisonnée, comme dans Blanche-Neige, son conte de fée préféré. [NB : L'histoire dit que cette pomme croquée inspira le logo de la marque Apple. En 2009, Gordon Brown a présenté les excuses du gouvernement britannique pour sa condamnation abominable.]

Turing fait donc partie de ces chercheurs géniaux et multicartes, ayant laissé leur empreinte et leur nom sur plusieurs domaines scientifiques différents (faisant mentir le zeroième théorème ?). Ses préoccupations scientifiques, ses interrogations philosophiques, l’ont amené à fonder des domaines en pleine expansion aujourd’hui. A ce titre, il aurait mérité le Nobel, mais ne l’aurait probablement jamais eu vu ses intérêts scientifiques plutôt dans le XXIe siècle que dans celui de l’ami Alfred.

Cliquer ici pour voir la vidéo.

>> Article initialement publié sur “Matières vivantes”

>> Illustration et vidéo Flickr CC : Leo Reynolds et Andrew Magill

>> Extrait du documentaire “The Genius of Alan Turing” en cours de tournage

De très nombreux blogs utilisent des CAPTCHA pour empêcher les robots spammeurs de mener leur sombre ouvrage. Ce joli nom aux consonances un peu soviétiques est l’acronyme de “Completely Automated Public Turing test to tell Computers and Humans Apart”, soit en bon français “test de Turing Public Complètement Automatisé permettant de reconnaître les Ordinateurs des Humains”.

Déchiffrer un CAPTCHA

Turing, l’un des grands génies multidisciplinaires du XXe siècle, avait proposé le test suivant : imaginez que vous chattiez avec deux interlocuteur inconnus, l’un étant un homme, l’autre une machine, comment feriez-vous pour les distinguer ? (dans un genre un peu différent il y a le fameux psy d’Emacs). A priori, plus la machine est intelligente, plus il va vous falloir du temps pour la distinguer de l’homme.

La voie la plus rapide est de tester les compétences analytiques et synthétiques de votre interlocuteur dans des domaines pour lesquels l’ordinateur est toujours bien inférieur à l’homme. Un exemple est la reconnaissance de formes, utilisée donc dans nos CAPTCHA : avant de pouvoir laisser un commentaire, l’interlocuteur doit reconnaître des caractères déformés, et les taper dans une fenêtre.

Si cette tâche est typiquement assez difficile pour un ordinateur, elle reste très facile pour l’homme, qui en une fraction de seconde mobilise les ressources de son puissant cerveau pour déchiffrer le CAPTCHA (et avoir le droit de laisser son commentaire pertinent ou son flame).

Du gâchis ? Plus maintenant !

Mais quel gâchis quand on y pense ! Tous les jours, 100 millions de CAPTCHA sont déchiffrés sur les blogs, sites, etc. C’est autant de tâches d’analyse complexe insolubles par des ordinateurs (par définition) et réalisées par des internautes. D’où l’idée derrière reCAPTCHA : “recycler” ce temps de calcul humain disponible gratuitement pour suppléer les ordinateurs sur les problèmes qu’ils ne savent pas à résoudre. Les détails de l’algorithme et la philosophie de la méthode sont exposés dans un article paru cette semaine dans la prestigieuse revue Science.

Le but du jeu ici est d’aider à la numérisation de livres, afin de préserver la connaissance humaine et de la rendre accessible au plus grand nombre. Les pages des livres sont scannées, et chaque mot est transformé en image bitmap par un logiciel approprié. Un autre logiciel de reconnaissance optique de caractères essaie ensuite de reconstituer le mot à partir de cette image.

Le problème est qu’environ 20% des mots ne peuvent être reconnus automatiquement par les logiciels. C’est là qu’entre en jeu reCAPTCHA : il utilise les capacités intellectuelles des internautes laissant des commentaires sur les blogs pour lire les mots que les ordinateurs ne peuvent pas lire.

En effet, reCAPTCHA vous demande de reconnaître deux mots pour pouvoir laisser un commentaire. Pour l’un des mots, reCAPTCHA connaît la réponse : il s’agit d’un des mots déjà déchiffrés par d’autres humains, mais non reconnaissable par un ordinateur. C’est sur ce mot-ci, appelé “mot de contrôle” qu’on testera si vous êtes vraiment un internaute ou un robot spammeur.

L’autre mot est le mot inconnu que l’ordinateur ne sait pas déchiffrer, le mot “test”. C’est sur ce mot qu’on vous mettra réellement à contribution : reCAPTCHA va comparer votre proposition aux propositions d’autres internautes sur ce mot. Si les trois premières personnes tombant sur ce mot proposent la même lecture et qu’il n’est pas reconnaissable automatiquement, ce mot est considéré comme déchiffré et sera utilisé comme mot de contrôle futur. Si les réponses humaines sont plus variables, ce mot reste comme un mot test et on additionne le nombre de possibilités proposées par les internautes pour ce mot. Dès qu’une proposition a plus de 2.5 voix [1] , ce mot est considéré comme lu.

Évidemment, il y a des cas où les mots ne sont pas du tout lisibles. Dans ce cas, vous pouvez demander un autre CAPTCHA à reCAPTCHA – il y a un petit bouton “reload” à côté du CAPTCHA. Si plus de six utilisateurs demandent à changer de CAPTCHA pour un même mot, le mot est considéré définitivement comme illisible et est sorti des bases de données de reCAPTCHA [2] .

L’ efficacité de reCAPTCHA a été évaluée sur 50 articles extraits des archives du New York Times entre 1860 et 1970, pour un total de 24 080 mots. 99.1 % des mots ont pu être déchiffrés par reCAPTCHA (216 erreurs), contre 83.5 % des mots pour de simples logiciels de reconnaissance automatique. Un taux de 99 % est en général le taux de réussite “professionnel” : pour l’anecdote, un des professionnels humains “témoin” travaillant sur les mêmes textes a effectué 189 erreurs, presque autant que reCAPTCHA.

Cependant, les erreurs de reCAPTCHA et les erreurs humaines sont de natures différentes : reCAPTCHA est plutôt sensible aux erreurs de “reconnaissance” des mots, par exemple le logiciel va couper des mots au milieu ou au contraire grouper des mots ensemble, tandis qu’un humain va “bêtement” se tromper en faisant une faute typographique ou orthographique…

reCAPTCHA fonctionne depuis 2007. Après un an, il avait été installé sur 40 000 sites web et 1.2 milliards de CAPTCHA avaient été déchiffrés, soit 440 millions de mots déchiffrés correctement. Si on considère que 25 % des mots dans un livre scanné sont mal reconnus, cela correspond à la bagatelle de 17 600 livres transcrits manuellement. En 2008, les créateurs de reCAPTCHA estimaient que l’équivalent de 160 livres par jour sont déchiffrés par reCAPTCHA, qui fournit l’équivalent du travail de 1 500 personnes déchiffrant un mot par seconde et travaillant 40 h par semaine.

En plus d’être utile, reCAPTCHA est plus efficace qu’un CAPTCHA traditionnel : en effet, les algorithmes des robots spammeurs peuvent “apprendre” à lire des CAPTCHA dans la mesure où les déformations habituelles sur les CAPTCHA sont faites numériquement. Or, les distorsions des mots imprimés sont beaucoup plus aléatoires, puisqu’il s’agit de “vraies” distorsions dues à des problèmes d’impression, des problèmes du papier, sans compter le bruit numérique dû au passage au scanner, etc.

Du crowdsourcing à toutes les sauces

Comme l’expliquent les auteurs, reCAPTCHA est la mise en pratique d’une idée fascinante, qu’ils appellent “human computation” (pouvoir de calcul humain ?). C’est une petite rupture dans notre vision de l’ordinateur : au lieu d’essayer d’améliorer les machines pour en faire des équivalents humains, tâche peut être simplement impossible à long terme, on utilise la puissance d’internet pour mettre en réseau des hommes afin de résoudre les problèmes complexes insolubles par la puissance de calcul brute des ordinateurs.

On parle ici de numérisation de livres, mais il existe aussi d’autres projets, comme Fold It, un jeu en ligne dans lequel les gens essaient de déterminer la structure des protéines, ou encore Galaxy Zoo dont nous avait parlé Dr Goulu. On peut imaginer que pour les grands défis numériques de demain, la mission de l’ordinateur ne sera alors que la mise en réseau et l’exécution en parallèle de tâches lourdes mais simples ; mais le vrai pouvoir de pensée, la vraie créativité resteront humaines.

J’aime bien cette idée également pour son corollaire un peu utopique. Qui pourra breveter une protéine dont la structure aura été trouvée grâce au calcul humain parallèle volontaire ? L’utilisation massive et volontaire des capacités des gens ne pourra pas être marchandisée, et le pouvoir de calcul humain deviendrait alors un pouvoir tout court, authentiquement démocratique …

[1] Une proposition d’un logiciel de reconnaissance optique de caractères comptant pour 0.5 voix
[2] Je suis personnellement un peu paresseux et j’ai tendance à abuser de ce bouton, dorénavant j’essaierai quand même de proposer quelque chose…

Références

• Le site de reCAPTCHA.
• Luis von Ahn, Benjamin Maurer, Colin McMillen, David Abraham, Manuel Blum, “reCAPTCHA: Human-Based Character Recognition via Web Security Measures“, Science 12 September 2008: Vol. 321. no. 5895, pp. 1465 – 1468
• Une vidéo d’une conférence de Luis von Ahn
• Enfin, Dr Goulu avait déjà publié deux billets sur le même sujet : les Ordinateurs Humains : des Captchas à PeekaSearch et ReCaptcha : quand l’internet utilise les cerveaux humains

Crédit photo CC FlickR par labguest

>> Ce billet a été initialement publié sur le blog de Tom Roud.