Dans le film de 1999 The Matrixla vie telle que nous la connaissons est en fait une abstraction de la réalité virtuelle ; une collection de zéros et de uns bien formés qui s’additionnent pour former une simulation tout à fait convaincante du monde réel. Savoir manipuler ce code – comme Morpheus, Trinity, Neo et les autres gentils patentés du film sont capables de le faire – leur permet de faire tout ce qu’ils veulent : lancer des mouvements de kung-fu fous, arrêter des balles en vol, plier des cuillères avec leur esprit ou sauter des immeubles d’un seul bond. En bref, il leur permet de réutiliser les calculs de la Matrice pour presque toutes les applications dont ils peuvent rêver.
Il y a plusieurs années, un informaticien d’une vingtaine d’années, Seth Hendrickson, a fait une démonstration étonnante (et pas tout à fait différente) en utilisant le jeu de plateformes à défilement latéral classique de Nintendo de 1990, Super Mario World. Comme beaucoup des membres les plus geeks de la Super Mario Hendrickson, connu sous le nom de « SethBling » sur sa célèbre chaîne YouTube, a été fasciné par la possibilité de pousser le jeu bien au-delà des limites imaginées par ses créateurs.
Hendrickson a injecté Flappy Bird331 octets de code dans Super Mario WorldIl a ensuite demandé au processeur de l’exécuter.
L’un des moyens d’y parvenir était de faire en sorte que sa console Super Nintendo lise les instructions de la RAM de la console au lieu de la cartouche de jeu originale. La RAM étant utilisée pour suivre toutes les parties de l’état du jeu, sa manipulation experte permet de créer des états de jeu entièrement nouveaux.
Plutôt que d’utiliser un codage traditionnel basé sur du texte, il est possible d’y parvenir en jouant au jeu lui-même ; en utilisant des éléments de jeu tels que la pose d’obus par Mario pour que le processeur lise certaines instructions d’une section de la RAM conçue pour suivre le placement de ces obus. Ces coordonnées étant stockées sous la forme d’une série d’octets, cela permet au pirate (Hendrickson dans ce cas) de contrôler ce que fait le processeur du jeu pendant quelques cycles d’horloge. Il peut ainsi s’emparer du code du jeu pour faire ce qu’il veut.
Vous ne comprenez pas ? C’est fort possible, mais croyez Hendrickson sur parole, cela fonctionne. Après avoir vu plusieurs exemples limités de ce piratage d' »exécution de code arbitraire » en action, Hendrickson a eu une idée. « L’ingénieur en moi savait que si l’on pouvait inciter le processeur à exécuter un petit peu de code, on pouvait l’inciter à exécuter beaucoup de code », a-t-il déclaré à Digital Trends.
Hendrickson s’est associé à un autre membre de la communauté, connu sous le nom de « p4plus2 ». Ensemble, ils ont montré qu’il était possible d’utiliser cette technique pour écrire un jeu entièrement nouveau à l’intérieur de l’ordinateur. Super Mario une architecture qui a été conçue pour, eh bien, Super Mario.
Ils ont choisi Flappy Bird, le jeu mobile follement addictif qui a connu un bref regain de notoriété en 2014. « [P4plus2] a écrit tout le code qui a fini par aller dans le Flappy Bird et j’ai fait la plupart du travail en développant les détails de la procédure et en m’exerçant pour pouvoir l’exécuter », explique Hendrickson.
« Bienvenue dans le monde de l’accidentellement complet de Turing. »
En répétant une série d’actions dans le jeu, comme un danseur créant une histoire par le mouvement, il a injecté… Flappy Bird331 octets de code dans Super Mario WorldIl a ensuite demandé au processeur d’exécuter ces octets en tant qu’instructions du processeur. Lorsqu’il a terminé, après une « planification méticuleuse » et « de nombreuses simulations », il a diffusé en direct l’intégralité de la démonstration à 12 000 spectateurs émerveillés sur Twitch. Cela reste le plus grand nombre de spectateurs simultanés que Hendrickson ait jamais eu.
Atteindre la complétude de Turing
« Bienvenue dans le désert du réel, » dit Morpheus dans The Matrix après avoir ôté la réalité simulée du monde virtuel et lui avoir montré la manipulation qui se cache en dessous. Dans le cas d’Hendrickson, la phrase pourrait être la suivante : « Bienvenue dans le monde de l’accidentellement complet de Turing. »
Atteindre la complétude de Turing ressemble à un état zen pour les programmeurs informatiques. En fait, il s’agit d’une caractéristique d’un système de calcul – une « machine de Turing universelle » – capable de calculer n’importe quoi, y compris un autre ordinateur sous une forme ou une autre. Hypothétisé en 1936 par Alan Turing, le père de l’informatique moderne, son concept de machine de Turing a défini ce que nous considérons aujourd’hui comme un ordinateur à usage général.
Une machine de Turing doit être capable d’effectuer des calculs en changeant d’état, en lisant et en écrivant sur une certaine forme de « bande », en déplaçant ladite « tête de bande » vers la gauche ou la droite, et en produisant une réponse finale sous la forme d’une « acceptation » ou d’un « rejet ». Chaque algorithme connu peut être converti en une machine de Turing et, par conséquent, peut être mis en œuvre dans n’importe quel système complet de Turing.
« A l’école primaire, je faisais des jeux dans PowerPoint pour m’amuser. »
Un système accidentellement complet de Turing est un système qui peut faire tout cela sans jamais le vouloir. Un système accidentellement complet de Turing pourrait être conçu pour, disons, guider un petit plombier italien à travers des niveaux de jeu pour sauver une princesse, mais il s’avère qu’il peut également être fait pour calculer les chiffres de pi, résoudre des puzzles sudoku, exécuter Microsoft Windows, ou presque tout le reste. C’est l’équivalent d’un citoyen ordinaire, vivant une vie de bureau mouvementée, qui découvre soudain qu’il ou elle est plus que ce qu’il ou elle pense. Ils sont Neo. Ils sont l’Unique.
« J’aime étonnamment [Turing complete] les démonstrations parce qu’elles témoignent souvent d’une ingéniosité considérable », a déclaré Gwern Branwen, qui tient en ligne des archives assez complètes de démonstrations complètes de Turing par accident. « Cela a de l’importance, poursuit-il, car, si l’on est ingénieux, cela permet de s’échapper d’un système qui est petit, prévisible, contrôlable et sûr – vers un système qui pourrait faire n’importe quoi. »
Plus d’informations sur ce sujet
Étant donné que Branwen héberge une archive entière de systèmes accidentellement complets de Turing, il n’est pas surprenant d’apprendre qu’il existe de nombreux autres exemples de systèmes accidentellement complets de Turing. Le jeu Pokémon Jaune s’avère être complet de Turing. Il en est de même pour Minecraftle grand classique de Windows, qui fait perdre du temps. Excel aussi. Et bien plus encore.
« À l’école primaire, je créais des jeux dans PowerPoint pour m’amuser », explique Tom Wildenhain, étudiant en informatique à l’université Carnegie Mellon. « Au départ, je m’en tenais à des choses simples comme des quiz à choix multiples et des labyrinthes, mais j’ai progressivement créé des jeux à la logique plus complexe. En fait, j’ai utilisé PowerPoint pour une tonne de tâches non liées à la présentation : édition d’images, animation 2D et conception de sites web. Au lycée, c’était une sorte de blague récurrente. Mes amis me disaient d’utiliser un ‘vrai logiciel’. »
À l’université, Wildenhain a suivi un cours théorique d’informatique où il a découvert les machines de Turing. J’ai pensé : « Je parie que PowerPoint pourrait faire cela », dit-il. Il s’avère que c’est possible, comme il l’a montré lors d’une démonstration effectuée pour une conférence de recherche fictive organisée chaque année le 1er avril à Carnegie Mellon. Cette conférence fictive présente des « réalisations de blagues sur des idées sérieuses et des réalisations sérieuses sur des idées de blagues ». « Une machine de Turing en PowerPoint semblait parfaitement adaptée », se souvient Wildenhain.
Le dernier exemple en date d’un système complet de Turing accidentel ? Le jeu de cartes geek préféré de tous Magic : The Gathering. « J’étais sur un forum de discussion lorsque quelqu’un a demandé si… Magic : The Gathering était complet selon Turing », a déclaré Alex Churchill, concepteur de jeux de société et codeur. « J’ai pensé : Qu’est-ce que ça peut bien vouloir dire ? »
Cue plusieurs années de recherche intéressée et un article récent qui démontre de manière convaincante l’idée.
Un badge d’honneur pour les geeks
Comme les exemples ci-dessus le suggèrent, il n’y a pas de pénurie de logiciels et de jeux accidentellement complets de Turing prêts et attendant d’être découverts. Alors, que faut-il chercher exactement lorsqu’il s’agit d’un système de Turing accidentellement complet ? Comme pour fouiller dans les vieilles reliques poussiéreuses d’un grenier, il existe quelques conseils qui aideront les chercheurs de trésors à trier les artefacts authentiques des déchets.
« De nombreux cas de découverte [Turing completeness] semblent consister à simplement remarquer qu’une primitive dans un système est un peu trop puissante ou flexible », a déclaré Branwen. « Par exemple, si la logique booléenne peut être implémentée, c’est un signe qu’il est possible d’en faire plus… [which can] transformer les circuits booléens en une logique de circuit complète pour une machine de Turing. Les substitutions, les définitions et les abréviations, les expressions régulières ou tout autre type de fonctionnalité de « recherche et remplacement » constituent un autre signal d’alarme, car ils suggèrent qu’un automate cellulaire ou un système de balises se cache. Cela s’applique à tout ce qui peut changer d’état en fonction des « voisins », comme une cellule de feuille de calcul ou un système de marquage. [even] un pixel ».
« Une fois que le génie de [Turing completeness] a été laissé sortir de la lampe, il est difficile de le faire revenir, et de rafistoler le goulot de la bouteille. »
Selon Alex Churchill, lorsqu’il s’agit de jeux de table, les candidats incluent les jeux qui permettent un nombre illimité de tours ou d’actions, qui sont capables de stocker au moins un nombre entier jusqu’à une taille théoriquement illimitée (ce qui exclut les jeux où les ressources sont limitées), qui permettent aux actions ou aux événements de s’enchaîner ou de se déclencher les uns les autres, et qui contiennent un moyen de contrôler ou de programmer quels événements entraînent la survenue de certains autres événements.
La plupart du temps, la découverte de la complétude accidentelle de Turing est plus un badge d’honneur pour les geeks qu’une application immédiate. Pour revenir une fois de plus à notre Matrice l’analogie, c’est plus l’équivalent du pliage de cuillère mental comme un tour de passe-passe après le dîner que c’est un bullet time destructeur conçu pour faire tomber l’ordre existant. En d’autres termes, avec de vrais ordinateurs à usage général disponibles, il n’y a pas d’obligation imminente de créer notre propre version non électronique en utilisant des jeux de cartes. Magic : The Gathering cartes.
Le problème avec Turing ?
Mais il y a encore des risques. Être capable de se réapproprier des outils ordinaires à des fins extraordinaires comporte des inconvénients potentiels. Nous n’avons pas tendance à considérer, par exemple, un fichier MS Word comme un programme capable de faire plus que nous aider à rédiger des documents de texte. Nous avons une idée fixe de ce qu’est un logiciel – et, plus important encore, de ce qu’il fait – et c’est à notre détriment.
La complétude de Turing met en lumière le fait que le calcul n’est pas quelque chose d’ésotérique qui n’existe que dans les langages de programmation ou les ordinateurs soigneusement configurés pour cette tâche. Si un jeu de cartes fantaisiste peut contenir les secrets du calcul, alors la complétude de Turing peut résider dans tout système raisonnablement complexe, à moins qu’on ne l’en empêche activement.
« Le fait que nous trouvions ces démonstrations surprenantes est en soi une démonstration de notre manque d’imagination et de compréhension des ordinateurs, de la sécurité informatique et de l’I.A. », a déclaré M. Branwen. « Nous prétendons que nous exécutons des programmes sur ces simples machines abstraites qui font ce que nous attendons intuitivement. Mais elles fonctionnent sur des ordinateurs qui sont bizarres, et nos programmes eux-mêmes se révèlent être des ordinateurs encore plus bizarres. »
Il pointe du doigt la vulnérabilité de sécurité Spectre, qui a pointé sa vilaine tête en 2018 et a procédé à des ravages. « Spectre a existé pendant des décennies dans des architectures de CPU qui ont été examinées de très près pour des problèmes de sécurité, mais qui sont juste en quelque sorte tombées dans un angle mort humain collectif », poursuit Branwen. Personne ne pensait que l’exécution spéculative contrôlable était un « ordinateur » qui pouvait être « programmé ». Une fois que quelqu’un l’a remarqué – parce qu’il était un ordinateur puissant et, bien sûr, complet selon Turing – il pouvait être utilisé de nombreuses façons pour attaquer des choses. »
Branwen suggère qu’à l’avenir, il y aura davantage de « machines bizarres » qui surgiront. « Les systèmes sécurisés doivent être construits par construction », a-t-il déclaré. « Une fois que le génie de [Turing completeness] a été laissé sortir de la lampe, il est difficile de le faire revenir, et de rafistoler le goulot de la bouteille. »
Pour l’instant, cependant, nous pouvons au moins joindre nos mains et nous émerveiller de la façon dont une paire de programmeurs informatiques intrépides a codé une version de l’algorithme de l’ADN. Flappy Bird à l’intérieur de Super Mario World.
Recommandations des rédacteurs