Gudule : Vous avez aimé la théorie des Schtroumpfs ? Vous avez tremblé pendant la Guerre des Alephs ? Vous avez frissonné en découvrant les Origines du Monstre ? Et maintenant, découvrez le nouvel épisode de la saga : les Machines de Turing !

Starring : le grrrand Christophe Nolim !

Euh, salut. En fait, je ne m'appelle pas vraiment Chris...

Starring : le grrrand Gudule !

Gudule, pourquoi un groupe agite-t-il des pancartes sous la fenêtre ?

Gudule : ne vous en faites pas, maître, ce sont mes fans. Je contrôle la situation.

Starring : le glorieux Flying Tortellini Monster !

FTM : je suis le créateur de l'univers !

Starring : Norbert le coléoptère !

Qu'est-ce qu'il fait là, celui-là ?

Norbert : je suis un coléoptère.

Starring : Alcibiade le yaourt !

Alcibiade : je suis malheureux.

Et préparez-vous à une révélation inattendue !

-----------------------------------------------------------

Une machine de Turing est un petit robot qui lit un ruban infini et possède un manuel d'instruction. À un instant donné, le robot peut être dans un certain état. Il a un nombre fini d'états possibles.

Sur le ruban se trouvent des caractères, disons 0 ou 1.

Le petit robot procède comme ceci :

– il lit un caractère

– il regarde son manuel d'instruction. Selon ce qu'il a lu, et selon l'état dans lequel il est, il effectue les trois opérations suivantes :

1. il change d'état

2. il se déplace

3. il écrit un caractère

Et il continue pour l'éternité tant qu'il n'est pas arrivé dans un état spécial, dans lequel il s'arrête, et meurt.

Gudule : pauvre petit robot.

Qu'est-ce qui est intéressant avec ce petit robot ? Eh bien son fonctionnement est purement mécanique, et peut être décrit mathématiquement, et il peut calculer tout ce que vous voulez.

Gudule, quelle est cette alarme qui sonne ?

Gudule : c'est l'alerte au génie, maître. Je venais justement de la réparer.

Diantre, nous avons détecté un génie dans les parages.

Gudule : c'est Turing, maître. C'est pour ça que ça sonne si fort.

En attendant qu'on éteigne l'alarme, micro-biographie de Turing. On n'aura jamais assez parlé de ce monsieur.

Turing est un mathématicien, informaticien, logicien, cryptanalyste, il est au panthéon des gens qui révolutionnaient la science au petit-déjeuner. Il a joué un rôle clé dans le déchiffrement (on ne dit pas décryptage) des messages encodés à l'aide de la machine Enigma, activité pour laquelle les premiers ordinateurs sérieux, des machines électromécaniques ingénieuses affectueusement nommées « bombes », ont été construits.

Enfin, c'est l'un des premiers théoriciens de l'intelligence artificielle et nous lui devons le bien connu test de Turing, celui dont l'objectif est de différencier un être humain d'une machine par le biais d'une discussion.

À part ça, c'était un homme avec des habitudes bizarres mais pas plus que d'autres mathématiciens, et un excellent marathonien.

En 1952, il est reconnu coupable d'homosexualité, ce qui est un crime au Royaume-Uni à cette époque, et pour éviter la prison, est contraint à une castration chimique ; il meurt en 1954 d'un empoisonnement au cyanure communément admis comme un suicide.

Si vous avez vu le film Imitation Game, je vous enjoins à retenir (et pareil si vous ne l'avez pas vu, ça ne change rien) qu'Alan Turing était un très, très grand génie, en plus d'avoir joué un rôle prépondérant dans la guerre des codes secrets qui a elle-même été déterminante dans la Seconde Guerre Mondiale. Et un exemple parmi d'autres que de nombreux grands hommes de science en leur temps ont été injustement bafoués par le monde qui les entourait ; pas seulement ceux qui fuyaient l'Allemagne nazie dans les années 30.

Gudule : ce chapitre est lugubre, maître.

Le film lui-même s'autorise un grand nombre d'écarts à la réalité, en particulier il fait de Turing un héros esseulé, incompris de ses pairs et en conflit avec sa hiérarchie. À ce qu'il me semble, s'il est vrai que tout le monde ne devait pas comprendre ce qui se passait dans la tête de ce monsieur, on le laissait en revanche faire son travail. À voir cependant pour la performance de Benedict Cumbernatch et parce que l'histoire, même déformée pour les besoins du scénario, mérite qu'on s'y intéresse.

La machine de Turing est donc l'archétype d'un ordinateur. Le robot est programmé (il y a des instructions qui lui disent ce qu'il faut faire), il y a une entrée (le ruban au début du calcul), et une sortie (le ruban à la fin du calcul). Je vous accorde que programmer une machine de Turing est une tâche fastidieuse et que le C++ est bien mieux. Gudule, ne prends pas cet air supérieur avec ta tasse de café à la main.

Sachez donc qu'au moment où Turing invente cette « machine », la notion d'ordinateur n'existe pas encore.

En fait, la notion de calcul mécanique existe déjà. Turing est fasciné par ce concept, mais il n'est pas le premier à se rendre compte qu'on peut calculer de manière automatique. Avant lui il y avait, entre autres :

– Blaise Pascal (1623 – 1662) qui invente une machine à calculer à 19 ans ; la pascaline (très bon scientifique, il a fini plus tard dans la théologie, comme vous le savez si vous avez lu les Pensées)

FTM : je ne cautionne pas cette dérive.

– Charles Babbage (1791 – 1871) qui a été le premier à imaginer utiliser les cartes perforées qui servaient aux métiers à tisser semi-automatiques de l'époque pour encoder des instructions à une machine de calcul à engrenages. Il n'a jamais construit sa machine en entier de son vivant, mais à partir des plans qui restaient, on a pu constater depuis qu'elle aurait parfaitement fonctionné. Cet homme était aussi un génie !

Gudule : maître, j'ai une question.

Vas-y, Gudule.

Gudule : tout le monde se prend d'affection pour le petit robot et son ruban. Mais... qu'est-ce qui nous prouve qu'il peut effectivement tout calculer ?

Intéressante question que tu as là, Gudule.

Gudule : c'était marqué sur le script, maître.

En effet, nous avons défini ce qu'est une machine de Turing et il nous faut maintenant démontrer que ce modèle peut bien tout calculer. En fait, il est possible de définir d'autres modèles mathématiques de calcul que les machines de Turing. Qui sont tous équivalents. Il est aussi possible de démontrer que les langages de programmation C, C++, Python et compagnie sont tous équivalents aux machines de Turing, ils ont exactement la même « puissance » de calcul, les mêmes capacités. On les dit « Turing-complets ». Cela te satisfait-il, Gudule ?

Gudule : meh...

Nous avons en fait déterré une affirmation qui n'est pas mathématique, mais philosophique. Ce qu'on appelle la thèse de Church (Alonzo Church était un mathématicien connu pour le lambda-calcul, un formalisme lié aux questions de calculabilité). Elle postule que :

Thèse de Church (formulation de Gudule) : tout ce qui est calculable, est calculable.

Ce qui veut dire : ce que vous pouvez calculer au sens de Turing, c'est-à-dire en utilisant une machine de Turing ou le C++, est exactement ce que vous pouvez calculer au sens usuel du terme, c'est-à-dire avec votre cerveau. Et exactement ce que vous pouvez calculer de manière physique, par des procédés mécaniques, par exemple avec une machine à la Babbage.

Gudule : pourquoi devrions-nous croire la thèse de Church ?

FTM : c'est peut-être un truc sur lequel je ne me suis pas planté.

En pratique, ça marche depuis 70 ans. De toute façon, nous sommes ici en maths, pas en physique. Une fois abstraite la notion de calcul, nous disposons d'une notion abstraite de calcul (que personne ne relève la lapalissade, c'est rhétorique). Et tous les théorèmes que nous énoncerons en informatique (calculabilité, complexité, etc. ) seront liés à cette notion de calcul.

Tout cela ne fait que commencer. Ce petit robot qui se promène sur son ruban va maintenant se révéler un outil absolu pour formaliser l'informatique.

----------------------------------

À suivre...