Vote électronique et fraude

On m'a signalé ce site, luttant contre le vote électronique :
http://recul-democratique.org/

Il y a des films de démonstration de fraudes; c'est assez effrayant. De la même façon, on peut assez facilement savoir pour qui vous votez en temps réel en captant les ondes radio émises par la machine.

Je ne peux que souscrire à ce genre d'arguments :

Dans une élection traditionnelle, pour limiter le risque de fraude, il suffit de surveiller les urnes le jour de l’élection (et quelques jours après s’il y a des litiges). Mais les ordinateurs de vote, c’est en permanence, à longueur d’année et vingt-quatre heures sur vingt-quatre, qu’il faut les surveiller, comme l’explique l’informaticien Pierre Muller [2] : « On a beau mettre sous clé l’ordinateur de vote dans les jours qui précèdent les élections, la machine peut être piratée à tout moment, par exemple six mois ou un an avant le scrutin. » Une telle surveillance étant quasi impossible, il suffit d’avoir la clé du local des ordinateurs et la complicité d’un informaticien, et hop, je t’embrouille. Ni traces, ni soupçon, ni contestation possible. De plus, poursuit Pierre Muller, « les composants informatiques sont standards et programmés à l’identique sur toutes les machines. Il suffit d’en modifier un, de le dupliquer, d’en préparer un lot à l’avance qu’il suffirait d’installer dans les ordinateurs de vote et toutes les conditions sont réunies pour une fraude massive ».

Deux trucs que je ne comprends pas bien :
- on est nécessairement obligé de reprogrammer la machine à chaque élection (vu qu'on ne vote pas pour les mêmes à chaque fois), qui s'occupe de cette programmation ? Comment être sûr qu'il n'y a pas de fraudes au moment de la reprogrammation ? L'avantage de l'urne transparente et des assesseurs des différents partis politiques, c'est que là au moins, il y a plusieurs témoins, ayant des intérêts divergents qui doivent s'équilibres,
- même sans intention de fraudes, on peut laisser des bugs dans des programmes. Après chaque programmation, j'espère que quelqu'un vérifie les programmes. Et vérifie au sens mathématique : il faut être absolument sûr que la machine donne réellement le résultat, quel que soit la séquence des votes. Je pense qu'il y a des méthodes standards (encore que ces méthodes sont nécessairement approchées, puisque la prédiction de l'issue d'un programme est il me semble indécidable, cf ce billet). Peut-être un informaticien peut-il m'éclairer, mais comment fait-on pour vérifier de tels programmes ? Le fait de savoir a priori si la machine donne le bon résultat quelle que soit la séquence des votes est-il mathématiquement décidable ?

Le "bêtisier" des partisans du vote électronique est lui aussi assez gratiné...

Platon, l'apprentissage et l'évolution

Extrait d'un ouvrage résumant l'héritage de Kolmogorov en physique :

Nous sommes capables d'apprendre par l'exemple et de classifier une multitude d'objets extérieurs en des catégories distinctes. (...) En deux mots, la difficulté qui se présente est la suivante : si une règle ne peut être logiquement déduite des exemples, comment se fait-il que nous puissions la trouver ? La solution mise en avant par Platon était que la règle est déjà contenue par le cerveau humain et que les exemples n'ont d'autre effet que de sélectionner la bonne règle parmi toutes celles qui sont admissibles.
Le point de vue opposé (Aristote) soutient que cette question est mal posée et que le cerveau humain est vide (tabula rasa) avant toute expérience sensible du monde extérieur.

Pour être plus concret, considérons la suite suivante : 01010101010101010. Si je vous demande quel est le prochain chiffre de la suite, tout être humain normalement constitué devrait en toute logique répondre 1. Le problème, c'est que cela n'a en fait rien de logique : il y a une infinité de suites différentes commençant par cette séquence, et la connaissance du début de cette séquence ne nous dit absolument rien sur ce qui suivra. Simplement, nous imaginons une règle : un 0 est suivi d'un 1, un 1 d'un zero. Nous testons ensuite cette règle sur l'exemple donné : elle marche à tous les coups. Donc cette règle nous paraît valable, et nous décidons (un peu) arbitrairement de la tenir pour acquise.

Cette méthode de pensée a l'air assez mécanique, voire un peu stupide quand on y réfléchit. Cependant, c'est un problème redoutable que de faire réaliser cet exercice simple à un ordinateur. A dire vrai, la seule méthode qui me paraît réellement efficace dans l'absolu est d'utiliser l'idée de Platon : générons des règles aléatoirement, puis testons-les sur nos exemples, et on devrait pouvoir arriver à trouver une (la?) véritable règle sous-tendant l'exemple. L'idée de "tabula rasa", si elle paraît au début plus élégante et moins arbitraire, apparaît dans la pratique bien peu réaliste : il paraît trop difficile d'un point de vue purement computationnel de créer quelque chose à partir de rien ...

Il est assez étonnant pour moi de constater les ponts entre ce débat Platon/Aristote, qui est en fait un débat inné/acquis, l'informatique et bien sûr la biologie. Luria et Delbruck ont en fait posé exactement la même question dans leur fameuse expérience : les bactéries sont-elles des "tabulae rasae", apprenant à resister à un stimulus, ou au contraire seules les bactéries ayant déjà la potentialité de resistance sont-elles effectivement sélectionnées ? Cette reformulation de l'idée de Platon est incroyablement proche du principe même de la sélection darwinienne : une règle admissible serait une mutation aléatoire, toutes deux étant sélectionnées par confrontation au réel. La théorie aristotélicienne serait au contraire une version lamarckienne de l'apprentissage. D'où une question qui se pose naturellement : le processus d'évolution ne serait-il pas d'avantage un processus d'apprentissage qu'un processus d'optimisation ?

La conséquence obervable de cette vision de l'évolution est l'existence d'étrangetés assez frappantes pour ceux qui considèrent la nature comme modèle de perfection : par exemple, ils est bien connu que l'oeil des mammifères est conçu en dépit du bon sens. Simplement, l'évolution de l'oeil a été longue et laborieuse, et des chemins de traverses ont été empruntés aboutissant à un instrument efficace sans être optimal. Qui n'a jamais utilisé des moyens détournés pour apprendre et retenir quelque chose ? En quelque sorte, la phrase mnémotechnique est à l'apprentissage ce que les organes vestigiels sont à l'évolution...

Maintenant, j'imagine qu'on peut généraliser cette idée à des processus plus actifs, comme par exemple la pensée même. Après tout, peut-on vraiment prétendre que nous sommes capables de concevoir une pensée originale par nous mêmes ? L'exercice de la pensée elle-même n'est-il pas plutôt un processus de mutation aléatoire/recombinaison/sélection ? Et si notre cerveau n'était qu'un bon gros générateur aléatoire couplé à un filtre éliminant les pensées les plus stupides ;) ?

Pensée et algorithmes génétiques

Je lis pas mal de livres sur l'optimisation numérique et ses liens avec les algorithmes génétiques en particulier. Je parcours en ce moment même Genetic Algorithms, in search, optimization and machine learning, de David E. Goldberg. Goldberg cite cet extrait d'un livre d'Hadamard , The psychology of invention in mathematical field :

We shall see a little later that the possibility of imputing discovery to pure chance is already excluded...On the conrary, that there is an intervention of chance but also a necessary work of unconsciousness, the latter implying and not contradicting the former... Indeed, it is obvious that invention or discovery, be it in mathematics or anywhere else, takes place by combining ideas

Ainsi Hadamard suggère-t-il que toute découverte est le processus d'une recombinaison aléatoire de pensées. L'homme sait ensuite reconnaître les pensées créatrices, les bonnes idées innovantes. C'est exactement le procédé à la base des algorithmes génétiques : le hasard est dans la recombinaison des différents génomes articifiels, ensuite, l'algorithme utilise une fonction de score pour évaluer l'adaptation des nouveaux circuits génétiques produits. Alors, le cerveau ne serait-il qu'une machine très perfectionnée permettant de recombiner les idées, puis d'évaluer la pertinence de celles-ci ? Autrement dit, le mécanisme de la pensée ne serait-il qu'un algorithme génétique un peu sophistiqué (*) ?


(*) Si l'on en croit le No Free Lunch Theorem, cela signifierait alors qu'il y aurait des domaines entiers tout simplement inconcevables par l'esprit humain, celui-ci étant adapté spécifiquement à certains problèmes. Poussons un peu plus loin le raisonnement pseudo-philosophique : j'imagine alors que les vérités accessibles par raisonnement sont les vérités démontrables, autrement dit tout ce qui peut être vérifié par une machine de Turing. Les vérités non accessibles par le raisonnement (non démontrables, non décidables) ne sont alors peut-être pas complètement inaccessibles, il s'agirait du domaine de l'intuition de Turing :

In his investigation, Turing introduced the idea of an ‘oracle’ capable of performing, as if by magic, an uncomputable operation. (...) An oracle is infinitely more powerful than anything a modern computer can do, and nothing like an elementary component of a computer. (...) But these oracle-machines are not purely mechanical. They are only partially mechanical, like Turing's choice-machines. Indeed the whole point of the oracle-machine is to explore the realm of what cannot be done by purely mechanical processes. Turing emphasised:

We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.

Turing's oracle can be seen simply as a mathematical tool, useful for exploring the mathematics of the uncomputable. (...) Thus Turing opened new fields of investigation in mathematical logic. However, there is also a possible interpretation in terms of human cognitive capacity. On this interpretation, the oracle is related to the ‘intuition’ involved in seeing the truth of a Gödel statement.

Jouer à Dieu

Je profite de mes actuelles insomnies new yorkaises pour lire et bloguer. Au détour d'un livre très intéressant de Gerhart et Kirschner, Cells, Embryos ans Evolution, j'ai découvert que Richard Dawkins ne se contentait pas d'écrire pour le grand public, mais menait aussi de vrais travaux de recherche. Ainsi a-t-il mis au point il y a un peu plus de 20 ans (une éternité dans le domaine de la biologie !) un programme sympathique permettant de générer des "biomorphs". L'idée est d'encoder un genome artificiel contrôlant le développement d'une créature virtuelle. Un jeu de mutations/sélection (où vous faites vous-mêmes la sélection) permet de créer des formes très variées, rappelant certaines formes naturelles. Je vous présente ci-dessus ma création d'insectes/sauterelles !
Au delà de l'intérêt esthétique, cet algorithme montre comment un génome a priori simple permet de générer (de façon émergente ou auto-organisée diraient certains) des formes complexes, et comment la sélection naturelle permet de changer rapidement ces formes - certaines transitions sont en effet assez spectaculaires.
A vous de jouer ici !

Le "No Free Lunch Theorem"

Il existe beaucoup de théorèmes d'impossibilités dans les sciences dures. L'exemple le plus connu est le fameux "théorème d'incomplétude de Gödel", affirmant en gros que certains énoncés ne peuvent être démontrés ou réfutés (voir aussi sur ce blog ce billet). Un des théorèmes assez récents dans le domaine de l'optimisation numérique ferait le malheur de Mike Slackenerny : il s'agit du "No Free Lunch Theorem". Ce théorème concerne les algorithmes d'optimisation numérique.
On passe notre vie à essayer optimiser quelque chose, à arbitrer entre plusieurs contraintes pour choisir ce qui nous semble le plus adapté. Par exemple, toute la microéconomie est basée sur l'idée d'optimisation sous contrainte, et le but du marché libre est de trouver un optimum collectif. Dans un registre plus légers, certains essaient de minimiser le nombre de mouvements à faire pour aller aux toilettes...
Mathématiquement, on définit alors une fonction de coût associée à un problème donné. La fonction de coût peut être très simple à définir : imaginons par exemple que vous soyez un représentant devant visiter plusieurs villes, et souhaitant minimiser votre fatigue, votre fonction de coût sera alors la distance totale parcourue. Il serait très utile, étant donnée une liste de villes, de connaître alors un moyen simple de minimiser cette distance totale. C'est un problème très classique en optimisation numérique : le problème du voyageur de commerce.
La plupart des scientifiques sont de gros paresseux, et aimeraient bien disposer de recettes toutes faites pour aborder ce genre de problème d'optimisation. Il serait formidable d'avoir une méthode générale, applicable à tous les problèmes sans exception, permettant d'optimiser à coup sûr une fonction de coût, quelle que soit sa forme, quel que soit le problème. Tout serait tellement plus simple... Et bien c'est peine perdue : le "No Free Lunch Theorem" affirme qu'une telle méthode n'existe pas. Le monde est trop complexe, et il n'existe pas de recette générale permettant d'optimiser n'importe quel problème. On peut formuler ce théorème de deux autres façons différentes :

• sur le gigantesque ensemble de tous les problèmes d'optimisation numérique, aucun algorithme n'est meilleur que les autres, i.e. le coût moyen (sur l'ensemble des problèmes) trouvé par un algorithme ne dépend pas de l'algorithme (et n'est donc pas le coût minimum a priori)

• Le seul moyen de trouver un algorithme plus efficace qu'un autre est d'adapter l'algorithme au problème, i.e. de connaître certaines structures mathématiques sous-jacente du problème d'optimisation permettant d'améliorer la performance de celui-ci.

La conclusion de tout ça, c'est que les numériciens et les spécialistes d'optimisation numérique ne seront jamais au chômage : chaque problème nécessite une étude approfondie et un algorithme spécifique pour être résolu. Ce genre de résultats affirme donc également que certains algorithmes très utilisés (par exemple les algorithmes génétiques, ou le recuit simulé) ne peuvent pas marcher de façon générale : ils ne seront efficaces que sur des problèmes avec des structures mathématiques bien précises. Je trouve également cette idée intéressante du point de vue de l'évolution : "l'algorithme" d'évolution darwinienne n'est efficace que s'il est adapté au problème ("sélection du plus adapté"). Si on connaît l'algorithme, cela signifie qu'on peut avoir des informations théoriques sur la structure du problème, et sur la fameuse "fitness function" chère aux biologistes...

Références :

Le papier original (merci Timothée) : Wolpert, D.H., Macready, W.G. (1997), No Free Lunch Theorems for Optimization, IEEE Transactions on Evolutionary Computation 1, 67.
Une démonstration assez simple du NFLT est proposée dans Ho, Y.C., Pepyne, D.L. (2002), Simple Explanation of the No-Free-Lunch Theorem and Its Implications, Journal of Optimization Theory and Applications 115, 549.

Avoir Internet dans l'upper East Side ....

A mon arrivée à New York il y a un an, je me disais qu'il me serait impossible de vivre sans Internet, que je ne pourrais jamais me passer de ce lien génial et indispensable avec la France. Les responsables de mon immeuble m'avaient alors garanti que d'ici à quelques semaines, tous les appartements seraient connectés à internet via l'université...

Un an après, la situation est totalement bloquée. En allant renouveler mon bail, sans surprise, j'ai appris que l'université avait renoncé et que je n'aurais jamais internet chez moi. Seulement le gros problème est que c'était l'un de mes seuls espoirs : aux Etats-Unis, à New York, à deux pas de Central Park et des Nations Unies, il n'est toujours pas possible d'avoir l'ADSL, comme le prouve la capture d'écran ci-contre. Et dans le temple mondial du capitalisme, impossible de faire jouer la concurrence à première vue : verizon est ici en position de monopôle local pour le téléphone.



Vous avez dit concurrence ? Ah oui, quand je suis arrivé, on m'a remis une feuille avec le nom des deux entreprises à contacter pour avoir respectivement le téléphone et le câble (oui, ici, les monopôles sont privés bien sûr). Verizon, donc, est hors course pour internet, après un an, j'en ai assez, je vais prendre internet sur le câble. Je me connecte donc chez Time Warner et consulte les informations sur leur plan Road Runner à 45$ par mois.

Tout commence bien : le câble est disponible dans mon immeuble, a priori c'est champagne. Sauf que en voulant faire la commande par internet une mauvaise surprise survient. Comme le prouve l'image ci-contre, avant de pouvoir commander son modem, il faut absolument cocher la case

"My computer meets the minimum system requirements."


"Requirements" en question qui sont :

Operating System Windows 98, 2000/ME/XP; Pentium-class 400 MHz processor; 64 MB RAM; 110MB of free hard drive space

MAC: System 9.x and higher; PowerPC; 32MB physical RAM w/Virtual Memory set to 40 MB; 30 MB free hard disk space

Et oui, je l'ai encore dans l'os étant sous debian linux. Autrement dit, je suis obligé d'avoir Windows ou un Mac pour pouvoir me connecter sur Internet à New York. Aux Etats-Unis, le pays le plus libéral du monde, j'ai donc eu successivement affaire à deux monopôles : celui du téléphone est incapable d'avoir des lignes en état pour fournir l'ADSL, celui du câble vous oblige par contrat à avoir certains systèmes d'exploitation pour pouvoir surfer sur le web.

Le pire est que contrairement à la France où j'avais pu sans problèmes télécharger tous les drivers de mon modem adsl sous linux, je ne trouve pas la moindre information sur le web ici pour configurer tout comme il faut.

Comme j'en ai ras-le-bol de ne pas avoir internet à la maison, je suis donc obligé de me lancer comme périodiquement dans de charmantes et agréables geekeries. Objectif : réinstaller windows sur une partition abritant une vieille Mandrake qui me servait en cas de défaillance de ma debian (chat échaudé craint l'eau froide). Comme je commence à avoir l'habitude de de genre d'exercice, la première étape consiste à ramasser le maximum d'informations pour savoir comment je vais réussir à réinstaller GRUB sur mon disque une fois que l'ogre Windows aura fait place nette sur mon MBR. J'ai maintenant Knoppix, une live CD de debian et un CD d'installation de Debian pour avoir le mode Rescue. Je vais bientôt tester le mode rescue pour voir comment se passe la réinstallation du GRUB. Après cela, installation de Windows XP (Arghhhhh!!!). A priori, si tout va bien ensuite restauration du GRUB et nouveau dual-boot, et à moi l'internet. Prions mes amis prions...

Edit 22:22 : c'est la berezina ! il faut que je reinstalle tout ! scrogneugneu....

Edit 7 Nov, 18:32 : bon, ça a l'air de remarcher à peu près correctement, modulo les problèmes classiques à chaque réinstallation (carte son à reconfigurer, souris USB non configurée) plus quelques nouveautés (skype et xfig buggés...). Heureusement, maintenant, j'ai mon dual boot !

Le petit pas d'Armstrong

Via Nature, une controverse linguistique résolue concernant le premier homme sur la Lune. En tant que francophone, nous avons tous en tête la fameuse phrase :
"C'est un petit pas pour l'homme, mais un grand pas pour l'humanité".
En fait, nous français avons légérement interprêté l'histoire, car les anglophones ont semblent-ils entendu lors de la retransmission en direct la phrase suivante :
"That's one small step for man, one giant leap for mankind."
, qui signifie en fait "C'est un petit pas pour l'Homme, mais un grand pas pour l'humanité", ce qui devient ridicule car "l'Homme" avec un grand H est synonyme de l'humanité dans ce contexte.

Néanmoins Armstrong avait préparé son coup et prévu de dire :
"That's one small step for a man, one giant leap for mankind."
qui a exactement le sens que nous avons retenu, nous français. De fait, Armstrong a toujours affirmé avoir bien prononcé l'article indéfini "a" qui change tout. Apparemment, des informaticiens se sont penchés sur le problème et ont démontré par l'analyse des bandes de l'époque qu'il avait effectivement prononcé la phrase prévue, grammaticalement correcte, mais que le bruit a sans doute occulté le "a" décisif. L'honneur est sauf !

Liens : un article qui résume toute l'histoire

Perl et moi

Je fais la plupart de mes simulations en C++.
Je trace des courbes sous gnuplot une centaine de fois par jour.
J'ai récemment découvert Matlab, et en suis totalemen fan (c'est très pratique pour faire du traitement d'image, des simulations numériques vite-fait bien-fait et des zolis films à glisser dans les présentations power-point... euh latex-beamer je veux dire).
Je fais mes figures roudoudesques sous xfig.
Je maîtrise même quelques secrets de mplayer et mencoder.
J'écris un peu moins régulièrement des scripts shells, mais je maîtrise à peu près.
Mais voilà...
Je crois que j'ai un problème avec Perl. A peu près tous les trois quatre mois, au détour d'un projet, je me retrouve à devoir traiter de façon systématique des tables données. Perl est alors tout indiqué. Le problème, c'est qu'en deux-trois mois, j'ai eu le temps d'oublier toute la syntaxe (assez obscure il faut bien le dire), tout pollué que je suis par les autres langages. Encore une fois, cet après-midi, il va falloir que j'exhume mon "Introduction to Perl" (honteusement piqué à ma môman, désolé maman...) aux fameuses éditions "O'Reilly" pour ré-apprendre la syntaxe de Perl... Mes vieux programmes aidant, peut-être un jour maîtriserai-je totalement cet outil !

Big finger

La reprise est active, plein de choses à faire, mais pas trop le temps d'écrire sur mon blog, désolé (j'ai pourtant de la matière en ce moment)... Cela ne risque pas de s'améliorer la semaine prochaine je le crains, mois de Septembre oblige. En attendant, je viens de réaliser un effet pervers de l'utilisation de la commande "finger".
Mode parano on
Logguez-vous sur la machine de vos collègues (ou plus pervers de votre patron), et tapez finger + nom du collègue. Vous aurez un compte rendu détaillé de ses activités récentes : mail, dernier log in... Par exemple, le matin, vous pouvez savoir à quelle heure le mail a été regardé pour la dernière fois, et savoir donc à peu près l'heure de départ (ou d'arrivée) du collègue en question, ou savoir s'il a bien lu le mail hyper urgent que vous lui aviez envoyé et auquel il n'a toujours pas répondu (malgré le fait qu'il ait lu son mail trois fois entre temps !!!). C'est horrible et pervers, nous sommes vraiment sous surveillance...
Mode parano off


Ajout 12 Septembre : je viens de voir en direct mon chef réaliser cette manip pour savoir si son étudiant avait lu son mail récemment... c'est horrible !

Scrogneugneu...

Juste un petit billet pour passer ma mauvaise humeur... Je viens de passer ma matinée à faire un beau programme Matlab, et souhaite tout compresser dans un fichier .zip. Je consulte donc les pages du manuel et tombe sur ça :

When given the name of an existing zip archive, zip will replace iden-
tically named entries in the zip archive or add entries for new names.
For example, if foo.zip exists and contains foo/file1 and foo/file2,
and the directory foo contains the files foo/file1 and foo/file3, then:

zip -r foo foo

will replace foo/file1 in foo.zip and add foo/file3 to foo.zip. After
this, foo.zip contains foo/file1, foo/file2, and foo/file3, with
foo/file2 unchanged from before.


Franchement, il fallait oser donner le même nom au fichier, au répertoire et à l'archive. Dans le genre peu clair... Les pages de manuel, c'est toujours comme ça et c'est vraiment nul. Des fois, j'en ai marre des geeks. Vivement que je m'achète un mac.
C'était la minute mauvais poil, je retourne bosser.

Web 2.0

Suite à cet article de Libé, je suis allé me perdre dans les méandres du soi-disant Web 2.0... et j'y ai trouvé des choses assez intéressantes, surtout pour nous linuxiens qui souffront régulièrement de la domination sans partage de Micro$oft . Ainsi, depuis techcrunch, j'ai découvert comment on pouvait lancer un émulateur d'office sur le web... Très impressionnant, on peut rédiger un .doc et le sauvegarder en local. Apparemment, on peut même faire du powerpoint avec un autre logiciel (je ne l'ai pas encore essayé toutefois...). Toutes ces applications semblent reposer sur une nouvelle technologie, appelée AJAX, acronyme pour Asynchronous JavaScript And XML, permettant de développer des applications web très interactives. Apparemment, l'idée générale qui se développe est de transférer sur le web tout ce que l'utilisateur lambda fait en local (traitement de texte, mail...). Jetez par exemple un coup d'oeil à NetVibes, sorte de portail configurable pour mettre à disposition tous vos besoins informatiques (fils RSS, blogs, e-mails, météo, shopping...) depuis un navigateur web. A priori, l'idée est séduisante, mais ai-je vraiment envie à titre personnel de stocker toutes mes données sur la toile (même sous accès hyper sécurisé ?). Une autre question me titille également : comment les boîtes émulant Office notamment, comptent-elles être rentables ?

Hello world !

Ouh la la, une semaine sans billet ! Rien ne va plus ! Rassurez-vous, je ne suis pas mort, mais juste en train d'approfondir ma connaissance de l'algorithmique et des automates cellulaires...
Parlons donc informatique pour une fois. Comme vous le savez sûrement, il existe des problèmes insolubles informatiquement (indécidables). L'exemple canonique de premier programme que tout un chacun étudie est le fameux "printf("hello, world\n");". Facile de savoir ce que fait cette simple ligne. Pourtant, ils est possible de démontrer qu'il est impossible de fabriquer un programme informatique qui testera à coup sûr si un programme écrira en sortie un "hello, world \n".

Démonstration par l'absurde : supposons qu'un tel programme H existe. Ce programme prend en entrée un programme P, un input d'exécution I de ce programme, et répond "oui" ou "non" selon que le programme affiche en sortie "hello, world\n". Soyons maintenant pervers : remplaçons le "non" en sortie par "hello, world\n". Considérons que I est le programme P lui-même, si bien que P se prend lui-même comme input. Appelons ce nouveau programme H modifié H' : H' renvoie donc ce qui arrive lorsqu'un programme P s'exécute avec son propre code en input, et répond "oui" si P exécuté sur lui-même affiche "hello, world\n" , et "hello, world\n" sinon. Prenons maintenant P=H', et évaluons s'il imprime "hello, world\n" à l'aide H'. Si cette exécution nous répond "oui", cela signifie que H' évalué avec H' comme input affiche "hello, world\n". Absurdité, il ne répond donc pas "oui" ! Maintenant, si H' évalué avec H' en input donne "hello, world\n", et bien la phrase magique est affichée, donc cette exécution doit renvoyer "oui". Deuxième absurdité.
Nous venons donc de démontrer par l'absurde qu'il est impossible de savoir si un programme affiche "hello, world\n" ! Vive l'informatique !

En photo : Alan Turing, père de l'informatique. Il s'est suicidé en mangeant une pomme empoisonnée... brrrrrr.....

Référence : Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman.

Crash

Non, je ne parlerai pas du film ayant remporté le plus prestigieux des oscars... mais il s'agit plutôt d'informer mon lectorat que j'ai eu quelques problèmes d'ordinateurs ces temps-ci. Ma partition /dev/hda8 sur laquelle était installée ma debian a rendu l'âme de façon incompréhensible, et j'ai passé ma journée à essayer de tout réinstaller. J'ai ainsi redécouvert les joies de la configuration du serveur X (sérieusement, c'est vraiment une cochonnerie, de quoi vous donner envie de retourner sous windows. Le même fichier xorg.conf tourne avec un noyau 2.4 mais ne tourne pas avec un noyau 2.6... J'ai également dû dégommer ma souris usb pour me contenter de mon touchpad, car le serveur x ne la trouvait pas et donc ne se lançait pas). Après moult efforts, tout a l'air de remarcher correctement, excepté la souris usb, donc, et mon micro qui est bien faiblard, ce qui me pose pas mal de problèmes pour skype - mais je soupçonne que le micro lui-même est détérioré, donc c'est plus un problème de hardware. Résultat des courses : aujourd'hui je n'ai quasiment rien fait, d'autant que c'était une journée d'entretiens pour futurs post-doc et que j'ai donc dû contribuer à la DRH scientifique du labo... Ca ira mieux demain !!

Science : Science de Normand

Je viens de lire un article tout à fait fascinant dans "Pour la science" de ce mois. Il concerne la fameuse conjecture "P=NP". L'auteur de l'article, Jean-Paul Delahaye (familier des vieux lecteurs de Science et Vie junior comme moi!), nous explique qu'une façon de démontrer cette conjecture serait de démontrer qu'elle est en fait indécidable ( c'est-à-dire qu'on ne peut démontrer dans le système d'axiome considéré qu'elle est vraie ou fausse). Cela ressemble à un syllogisme ! Il cite un exemple très précis en arithmétique - considérons la conjecture suivante, dite conjecture de Goldbach : "Tout nombre pair supérieur à 4 est somme de deux nombres premiers". Si cette proposition est indécidable, on ne peut démontrer qu'elle est fausse. Or, une façon très simple de démontrer qu'elle est fausse serait de trouver un contre-exemple. Donc, si la conjecture est indécidable, cela signifie qu'on ne peut trouver de contre-exemple, donc qu'elle est vraie ! Du coup, la proposition serait-elle en fait décidable ? Je ne le pense pas : l'indécidabilité dans le sens "vrai" signifie à mon avis qu'on ne pourrait vérifier le résultat qu'en énumérant tous les cas - autrement dit qu'il n'y aurait pas de raisons "profondes" dans le système d'axiome considéré permettant de l'établir. Cette énumération est évidemment impossible car le nombre de cas est infini, d'où l'indécidabilité. Je crois d'ailleurs que lorsque le nombre de cas est fini (ou pas trop grand !), les informaticiens n'hésitent pas à énumérer tous les cas pour "démontrer" certains énoncés.

Ce mode de raisonnement basé sur l'indécidabilité pourrait donc peut-être s'appliquer à tout résultat très général portant sur des ensembles infinis, pouvant être réfuté simplement par un contre-exemple. Ainsi, si la conjecture de Riemann est indécidable, elle est vraie, car on ne peut alors trouver de contre-exemple, et de même peut-être pour la conjecture "P=NP" !

Science : Prospective informatique 2

Suite de mes quelques considérations sur l'informatique, pour vous parler de l'accueil réservé à quelques innovations informatiques à travers deux exemples. Autrefois, bien avant l'invention de nos OS préférés, les ordinateurs étaient programmés à l'aide de cartes perforées (un peu comme ces pianos que l'on peut voir parfois dans les westerns !). Lorsque les premières interfaces sont apparues, elles n'ont semble-t-il pas fait l'unanimité dans la communauté scientifique : il était alors plus facile de changer simplement la position de certains trous pour relancer la simulation numérique plutôt que de s'encombrer avec une interface probablement lourde et lente. De la même façon, un peu plus tard, lorsque la souris est apparue, son intérêt n'était pas des plus évidents : l'utilisation de raccourcis claviers permettait sans peine de suppléer à ce nouvel engin barbare, surtout qu'un simple Control+x+s est bien plus rapide qu'un File, Save maladroitement cliqué au mulot. Pourtant, il est assez inimaginable de se passer aujourd'hui de ces innovations fondamentales. Finalement, le problème essentiel de ces méthodes à l'ancienne est qu'elles nécessitaient sans aucun doute un long apprentissage avant de pouvoir s'en servir efficacement.



L'informatique grand public a complètement révolutionné la façon de concevoir les ordinateurs : d'une certaine manière, l'efficacité passait en second, l'ordinateur devait devenir avant tout accessible et intuitif. Evidemment, pour les scientifiques, cela devait passer pour une hérésie. Heureusement, les progrès technologiques en parallèle ont été tels qu'on a pu avoir le beurre et l'argent du beurre : à la fois les performances et la facilité d'utilisation, même s'il existe encore un certain nombre de logiciels conçus à l'ancienne qui n'ont pas été encore supplantés. Par exemple Latex règne toujours en maître pour le traitement de texte mathématique, même s'il n'arrivera jamais selon moi à s'imposer pour le traitement de texte classique sans évolution majeure dans le sens du grand public. D'ailleurs, Latex lui-même est une évolution de l'obscur Tex, ce qui prouve que les concepteurs de logiciels (en particulier libres) ont bien compris la nécessité de s'adapter au plus grand nombre pour pouvoir survivre...

Science : Prospective informatique 1

Chers lecteurs de ce blog (le s est-il vraiment nécessaire ?),

quelques billets pour vous faire part d'une conversation amusante que j'ai récemment eue avec mon directeur de thèse (il me faut préciser pour les potentiels lecteurs de ce blog qui ne sont pas de mes proches que je suis en toute fin de thèse de physique et que je soutiens le 16 Septembre. Ugh...). J'ai vu dans ma prime jeunesse tout au long des années 80 et 90 l'essor de l'informatique personnelle (je me souviens encore avec excitation et émotion du jour où mon père a ramené à la maison un TO7). Je croyais naivement qu'avant cette époque glorieuse, l'informatique -en France en tous cas- n'était reservée qu'à une élite fortunée et/ou militaire et que de gigantesques machines type Eniac (cf photo) calculaient jour et nuit d'obscures quantités liées à une potentielle guerre nucléaire. Que nenni ! L'informatique avait déjà fait depuis longtemps son entrée dans les labos de recherche. Mon directeur de thèse a même été l'un des tous premiers à taper sa thèse sur traitement de texte, à l'aide d'un concurrent aujourd'hui disparu de Tex. Pour l'anecdote, l'ordinateur du labo auxquel étaient reliés tous les terminaux occupait la totalité de la salle où travaillent actuellement les thésards (faut-il y voir une certaine continuité historique 8^) ? ). Plus surprenant, jusqu'à assez récemment, l'un des défis potentiels était de concevoir et de construire des ordinateurs pouvant résoudre spécifiquement des problèmes très précis donnés. Par exemple, un ordinateur pouvant calculer précisément des comportements liés aux transitions de phase (type eau-glace) , ou pouvant simuler très efficacement tel ou tel problème de physique des fluides. L'idée séduisante était d'optimiser l'architecture et les langages pour pouvoir commercialiser et utiliser au quotidien un super-ordinateur pouvant réaliser une opération très précise donnée.

Evidemment, ces projets très lourds et très couteux sont vite devenus caducs compte-tenu de la croissance exponentielle des capacités de calcul. Dès le début des années 90, n'importe quel PC du commerce écrabouillait de plusieurs ordres de grandeur en terme de puissance de calcul toute machine hyper optimisée de l'époque. Une anecdote pleine de sens à mon avis à l'heure où l'on souhaite orienter davantage la recherche française vers l'application (l'innovation comme on dit...)
A suivre ...

PS : pour ceux qui veulent en savoir un peu plus sur l'histoire de l'informatique, je conseille ce site.