Billard et machine de Turing : une bille suffit à exécuter n’importe quel calcul

1 bille, 2 dimensions, 0 pièce mobile. Un billard plan à parois fixes, parcouru par une seule bille, simule n’importe quelle machine de Turing : Eva Miranda et Isaac Ramos l’ont démontré dans les PNAS du 15 septembre 2026. Miranda enseigne à l’Universitat Politècnica de Catalunya, Ramos à l’ETH Zurich. Leur article de revue ne contient ni circuit, ni horloge, ni transistor.

Cristopher Moore avait posé la question en 1990, en supposant qu’un billard à plat manquait de place pour calculer. Les constructions venues ensuite lui ont donné raison en ajoutant des pièces : plusieurs billes, des parois en trois dimensions, des murs mobiles, une mémoire logée dans la vitesse de la particule. Aucun de ces ingrédients n’est nécessaire, tranche le texte de la preuve : une particule, deux dimensions et des bords fixes suffisent.

« Turing-complet » veut dire une chose précise : tout ce qu’un ordinateur sait calculer, ce système le calcule aussi. Pas plus vite. Pas mieux. Tout, simplement. Le billard rejoint cette catégorie sans rien emprunter à l’électronique.

Ce que la bille écrit en roulant

Concrètement, la mémoire de la machine tient dans la position de la bille sur un segment : un nombre entre 0 et 1, écrit en base 3. Les décimales de rang impair portent la moitié droite du ruban, celles de rang pair la moitié gauche. Rien n’est stocké ailleurs, toute la mémoire de la machine est une coordonnée. Lire revient à mesurer où la bille touche le segment. Écrire revient à la renvoyer ailleurs.

Les murs font le reste. Des paraboles partageant un même foyer déplacent la tête de lecture d’une case. Des parois de contrôle au profil ondulé exécutent les lectures et les écritures. Ces ondulations se répètent à des échelles de plus en plus fines : imaginez une règle graduée qui continuerait de se subdiviser sous chaque graduation, sans fin.

Le programme, c’est la forme des murs. Miranda insiste sur ce déplacement dans le communiqué du centre : « Le calcul ne se fait pas au niveau des flippers, il se fait dans la forme de la paroi. » Un flipper, ajoute-t-elle, « n’est pas une surface, c’est un catalogue de pièces boulonnées les unes à côté des autres ».

Pourquoi votre ordinateur ne craint rien

Personne ne fabriquera cette table. Elle reste bornée et sa frontière lisse par morceaux, mais chaque paroi de contrôle assemble une infinité dénombrable de segments droits. Le dessin descend à des échelles arbitrairement fines, et aucune fraiseuse ne descend à l’infini. Les auteurs proposent une porte de sortie théorique : un billard s’obtient comme limite de systèmes hamiltoniens lisses, en remplaçant les murs durs par des potentiels qui divergent au bord.

Le second garde-fou est d’une autre nature. Puisque la trajectoire simule une machine de Turing, savoir si elle finit par se refermer revient à savoir si la machine s’arrête. Le calcul s’arrête : la bille rejoint le segment d’arrêt et son orbite devient périodique. Le calcul ne s’arrête pas : l’orbite ne se referme jamais. Aucun algorithme ne peut donc décider, en général, si une trajectoire partant d’un point calculable est périodique. Simple chaos ? « Le chaos impose une barrière de précision ; l’indécidabilité impose une barrière logique », distingue Miranda.

L’intérêt de la preuve dépasse largement la table de jeu. Les billards servent de modèles idéalisés au mouvement de particules qui rebondissent élastiquement, et ils apparaissent comme limites de systèmes hamiltoniens. Des trajectoires indécidables existent donc dans des modèles physiquement naturels, y compris ceux des gaz de sphères dures et des chaînes de collisions en mécanique céleste. Pour la mécanique céleste, une marche reste à franchir : prouver que des orbites gravitationnelles suivent le calcul indéfiniment, et pas seulement sur un intervalle fini.

Le fil rejoint celui d’un ordinateur quantique mis à démontrer que les diagonales d’un carré se croisent à angle droit : une machine improbable éclaire la frontière du calculable mieux qu’une machine rapide. Miranda regarde déjà de ce côté. Sa question : en passant au quantique, l’indécidabilité disparaît-elle, ou change-t-elle seulement de place ? Son hypothèse est qu’elle change de place.

Article créé en collaboration avec l’IA.