Comment construire un ordinateur Origami | Magazine Quanta

En 1936, le mathématicien britannique Alan Turing a eu l’idée d’un ordinateur universel. C'était un appareil simple : une bande infinie de ruban recouverte de zéros et de uns, ainsi qu'une machine qui pouvait se déplacer d'avant en arrière le long de la bande, changeant les zéros en uns et vice versa selon un ensemble de règles. Il a montré qu’un tel appareil pouvait être utilisé pour effectuer n’importe quel calcul.

Turing n’avait pas l’intention que son idée soit pratique pour résoudre des problèmes. Au contraire, il s’agissait d’un moyen inestimable d’explorer la nature du calcul et ses limites. Au cours des décennies qui ont suivi cette idée fondatrice, les mathématiciens ont dressé une liste de schémas informatiques encore moins pratiques. Des jeux comme Minesweeper ou Magic: The Gathering pourraient, en principe, être utilisés comme ordinateurs à usage général. Il en va de même pour les soi-disant automates cellulaires comme celui de John Conway Le jeu de la vie, un ensemble de règles pour faire évoluer des carrés noirs et blancs sur une grille bidimensionnelle.

En Septembre 2023, Inna Zakharevitch de l'Université Cornell et Thomas Hull du Franklin & Marshall College a montré que tout ce qui peut être calculé peut être calculé en pliant du papier. Ils ont prouvé que l’origami est « Turing complet », ce qui signifie que, comme une machine de Turing, il peut résoudre n’importe quel problème informatique traitable, avec suffisamment de temps.

Zakharevich, un passionné d'origami depuis toujours, a commencé à réfléchir à ce problème en 2021 après être tombé sur une vidéo expliquant l'intégralité du jeu de la vie de Turing. "Je me disais que l'origami est beaucoup plus compliqué que le jeu de la vie", a déclaré Zakharevich. "Si le jeu de la vie est terminé par Turing, l'origami devrait également l'être."

Mais ce n'était pas son domaine d'expertise. Même si elle plie l'origami depuis qu'elle est jeune – « si vous voulez me donner un truc super complexe qui nécessite une feuille de papier de 24 pouces et comporte 400 étapes, je suis partout dans ce truc », a-t-elle dit – elle la recherche mathématique portait sur les domaines beaucoup plus abstraits de la topologie algébrique et de la théorie des catégories. Elle a donc envoyé un e-mail à Hull, qui étudiait les mathématiques de l'origami à plein temps.

"Elle vient de m'envoyer un e-mail à l'improviste, et je me demandais pourquoi un topologue algébrique me pose des questions à ce sujet ?" dit Hull. Mais il réalisa qu'il n'avait jamais réellement réfléchi à la question de savoir si l'origami pouvait être complet à Turing. "Je me disais, c'est probablement le cas, mais je ne sais pas vraiment."

Alors lui et Zakharevich ont décidé de prouver qu'on pouvait fabriquer un ordinateur avec de l'origami. Ils ont d’abord dû coder les entrées et sorties informatiques – ainsi que les opérations logiques de base comme AND et OR – sous forme de plis de papier. S’ils pouvaient ensuite montrer que leur système pouvait simuler un autre modèle informatique déjà connu pour être complet à Turing, ils atteindraient leur objectif.

Une opération logique prend en compte une ou plusieurs entrées (chacune écrite comme VRAI ou FAUX) et génère une sortie (VRAI ou FAUX) basée sur une règle donnée. Pour réaliser une opération avec du papier, les mathématiciens ont conçu un diagramme de lignes, appelé motif de pli, qui précise où plier le papier. Un pli dans le papier représente une entrée. Si vous pliez le long d'une ligne du motif de pli, le pli se retourne d'un côté, indiquant une valeur d'entrée TRUE. Mais si vous pliez le papier le long d’une ligne différente (à proximité), le pli se retourne sur le côté opposé, indiquant FAUX.

Deux de ces plis d’entrée alimentent un ensemble complexe de plis appelé gadget. Le gadget code l'opération logique. Afin de réaliser tous ces plis tout en permettant au papier de se plier à plat – une exigence imposée par Hull et Zakharevich – ils ont inclus un troisième pli qui est forcé de se plier d'une manière particulière. Si le pli s'inverse dans un sens, cela signifie que le résultat est VRAI. S'il s'inverse, le résultat est FAUX.

Les mathématiciens ont conçu différents gadgets qui transforment les entrées en sorties selon diverses opérations logiques. "C'était beaucoup de jouer avec du papier et de s'envoyer des photos… puis d'écrire des preuves rigoureuses que ces choses fonctionnaient comme nous le disions", a déclaré Hull.

On sait depuis la fin des années 1990 qu'un système plus simple analogique unidimensionnel du jeu de la vie de Conway est Turing terminé. Hull et Zakharevich ont compris comment écrire cette version de Life en termes d'opérations logiques. "Nous n'avons finalement eu besoin que de quatre portes : AND, OR, NAND et NOR", a déclaré Zakharevich, faisant référence à deux portes simples supplémentaires. Mais pour combiner ces différentes portes, ils ont dû construire de nouveaux gadgets qui absorbaient les signaux parasites et permettaient aux autres signaux de tourner et de se croiser sans interférer les uns avec les autres. "C'était la partie la plus difficile", a déclaré Zakharevich, "trouver comment tout s'aligner correctement". Après qu'elle et Hull aient réussi à assembler leurs gadgets, ils ont pu encoder tout ce dont ils avaient besoin dans des plis de papier, montrant ainsi que l'origami est complet pour Turing.

Un ordinateur origami serait extrêmement inefficace et peu pratique. Mais en principe, si vous aviez une très grande feuille de papier et beaucoup de temps libre, vous pourriez utiliser l'origami pour calculer arbitrairement de nombreux chiffres de $latex pi$, déterminer la manière optimale d'acheminer chaque chauffeur-livreur dans le monde, ou exécuter un programme pour prédire la météo. "En fin de compte, le motif de plis est gargantuesque", a déclaré Hull. "C'est difficile à plier, mais cela fait le travail."

Pendant des décennies, les mathématiciens ont été attirés par l’origami parce que « cela semblait amusant et inutile », disait-il. Erik Demaine, informaticien du Massachusetts Institute of Technology qui a largement contribué aux mathématiques de l'origami. Mais récemment, il a également attiré l’attention des ingénieurs.

Les mathématiques de l'origami ont été utilisées pour concevoir d'énormes panneaux solaires pouvant être pliés et transportés dans l'espace, des robots qui nagent dans l'eau pour collecter des données environnementales, des stents qui voyagent dans de minuscules vaisseaux sanguins, et bien plus encore. "Maintenant, des centaines, voire des milliers de personnes utilisent tous les calculs et algorithmes d'origami que nous avons développés pour concevoir de nouvelles structures mécaniques", a déclaré Demaine.

Ainsi, « plus nous ferons des choses comme celle-ci », a déclaré Hull, « plus nous aurons de chances, je pense, d’établir des croisements profonds entre l’origami et des branches bien établies des mathématiques. »