🤖 machine learning

A PyTorch Library of Turing-Complete Neural Networks

Cet article présente une bibliothèque PyTorch qui compile les descriptions de machines de Turing en simulations de réseaux de neurones exactes et sans entraînement, en utilisant deux architectures distinctes : un transformateur fondé sur Wei et al. (2021) et un réseau récurrent fondé sur Siegelmann et Sontag (1995).

Auteurs originaux : Jonathan Bates

Publié 2026-05-12

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jonathan Bates

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous ayez une recette pour une danse très spécifique et complexe. Habituellement, pour enseigner cette danse à un robot, vous lui montreriez les mouvements des milliers de fois et vous le laisseriez « apprendre » par essais et erreurs. Mais que se passerait-il si vous pouviez simplement remettre au robot un plan indiquant : « Si vous voyez l'étape A, faites le mouvement B ; si vous voyez l'étape C, faites le mouvement D », et que le robot puisse exécuter la danse parfaitement dès la première tentative, sans jamais s'entraîner ?

C'est exactement ce que fait cet article, mais au lieu d'une danse, il s'agit d'enseigner à un réseau de neurones (un type d'IA) à se comporter comme une Machine de Turing — le « cerveau » théorique derrière tous les ordinateurs modernes.

Voici le détail de la méthode employée, en utilisant des analogies simples :

1. La Grande Idée : « Compiler, ne pas entraîner »

La plupart des IA actuelles ressemblent à un étudiant qui révise pour un examen en lisant un manuel scolaire encore et encore. Cet article présente un package (un ensemble d'outils pour les programmeurs) qui agit davantage comme un traducteur. Vous lui donnez les « règles » d'un programme informatique (la Machine de Turing), et il écrit instantanément les « poids » (les paramètres internes) d'un réseau de neurones afin que le réseau connaisse parfaitement les règles dès le départ. Pas d'étude, pas de devinettes, pas d'entraînement requis. Il est « correct par construction ».

2. La Boîte à Outils : Construire la logique à partir de zéro

Pour créer ce traducteur, les auteurs ont dû montrer comment un réseau de neurones peut effectuer des opérations mathématiques et logiques de base, tout comme une calculatrice.

Les Briques (Portes logiques) : Ils ont montré comment construire de simples « interrupteurs » (comme ET, OU, NON) à l'intérieur du réseau. Imaginez-les comme de minuscules interrupteurs lumineux qui s'allument ou s'éteignent selon des conditions spécifiques.
Le Plan (Forme normale disjonctive) : Ils ont organisé ces interrupteurs selon un motif spécifique (comme un organigramme) capable de décrire n'importe quelle règle que l'ordinateur doit suivre.
La Calculatrice (Additionneurs) : Ils ont construit un additionneur numérique à l'intérieur du réseau. Cela permet à l'IA de compter vers le haut ou vers le bas, ce qui est essentiel pour qu'un ordinateur sache où il se trouve sur son « ruban » (mémoire).

3. Deux Façons Différentes de Construire la Machine

L'article propose deux « plans » (architectures) différents pour transformer ces règles en une IA fonctionnelle.

Plan A : Le Transformer (Le « Super-Lecteur »)

Cette version est basée sur une architecture d'IA moderne appelée Transformer (le même type utilisé dans les chatbots).

Fonctionnement : Imaginez un bibliothécaire possédant un immense livre d'histoire. Chaque fois que l'ordinateur doit faire un mouvement, le bibliothécaire revoit tout ce qui s'est passé auparavant pour trouver le bon indice.
L'Astuce : Il utilise un mécanisme spécial d'« attention dure ». Au lieu de deviner vaguement quel événement passé est important, il agit comme un pointeur laser, se verrouillant exactement sur une seule pièce d'information spécifique du passé pour prendre sa décision.
Le Résultat : Il simule l'ordinateur étape par étape, se souvenant parfaitement de l'historique du ruban et de l'état actuel.

Plan B : Le Réseau Récurrent (La « Pile d'Assiettes »)

Cette version est basée sur des recherches plus anciennes des années 1990.

Fonctionnement : Au lieu d'un long ruban, cette machine considère la mémoire comme une pile d'assiettes (comme un plateau à ressort dans une cafétéria).
La Magie Mathématique : Les auteurs utilisent une astuce mathématique ingénieuse appelée Ensemble de Cantor. Imaginez comprimer une pile infinie d'assiettes en un seul nombre entre 0 et 1.
- Ajouter une assiette (pousser) équivaut à multiplier ce nombre.
- Retirer une assiette (popper) équivaut à le diviser.
Le Problème : Comme cela repose sur le fait de comprimer une information infinie en un seul nombre, cela est très sensible aux erreurs d'arrondi. Cela fonctionne parfaitement en théorie, mais sur un ordinateur réel, si vous empilez trop d'assiettes, le nombre devient trop désordonné pour être lu avec précision.

4. Pourquoi Cela Compte (Selon l'Article)

Les auteurs ne prétendent pas que cela rendra votre téléphone plus rapide ou guérira des maladies. Au contraire, ils offrent une preuve de concept et une boîte à outils :

Un Pont : Il relie le monde des mathématiques pures (logique et machines de Turing) au monde des réseaux de neurones.
Une Référence : Il fournit aux chercheurs un exemple parfait et exécutable à étudier.
Vérification de la Stabilité : Comme le réseau est construit parfaitement à la main, les scientifiques peuvent désormais tester ce qui se passe si vous « poussez » légèrement les paramètres (comme en ajoutant du bruit ou en essayant de l'affiner). La machine parfaite se brise-t-elle ou reste-t-elle stable ?

Résumé

Considérez cet article comme un manuel d'usine. Il ne dit pas simplement « L'IA peut faire des mathématiques ». Il dit : « Voici les instructions exactes de la chaîne de montage pour construire une machine qui fait des mathématiques parfaitement, en utilisant uniquement les matières premières des réseaux de neurones ». Il prouve que si vous connaissez les règles, vous pouvez construire la machine instantanément, sans avoir besoin de lui apprendre comment apprendre.

Résumé technique : Une bibliothèque PyTorch de réseaux de neurones Turing-complets

Énoncé du problème

Bien que la littérature théorique ait depuis longtemps établi que les réseaux de neurones peuvent simuler des machines de Turing (MT) — notamment par le biais de réseaux récurrents (Siegelmann & Sontag, 1995) et de transformateurs avec attention dure (Pérez et al., 2021 ; Wei, Chen, & Ma, 2021) — un fossé important subsiste entre les preuves mathématiques spécifiant des matrices de poids et des implémentations concrètes et exécutables. Les preuves existantes reposent souvent sur une précision infinie ou des constructions abstraites difficiles à instancier dans les cadres d'apprentissage profond standard. Cet article répond au besoin d'une « référence concrète et exécutable » qui fait le pont entre les domaines symbolique et neuronal en compilant directement une description de machine de Turing en un réseau de neurones aux poids fixes et interprétables, ne nécessitant aucun entraînement.

Méthodologie

Les auteurs présentent un package PyTorch qui construit des réseaux de neurones à partir d'une fonction de transition de MT ( $\delta$ ) donnée et d'un ensemble d'états terminaux. La compilation procède par une hiérarchie de composants, garantissant que le passage avant du réseau implémente exactement une étape de la machine spécifiée. Deux architectures distinctes sont implémentées, chacune réalisant un résultat théorique différent :

1. Composants de base

La construction repose sur l'assemblage de logique complexe à partir de portes de base activées par ReLU :

Logique booléenne : L'article démontre comment les réseaux ReLU implémentent des portes élémentaires (ET, OU, NON, OU exclusif) et les compose en circuits de forme normale disjonctive (FND).
Fonction de transition : La table de recherche finie $\delta$ est réalisée comme un circuit FND à deux couches, où un neurone caché existe pour chaque paire état-symbole.
Arithmétique binaire : Des additionneurs à propagation de retenue, construits à partir de demi-additionneurs et d'additionneurs complets, sont utilisés pour mettre à jour la position de la tête (incrémentant ou décrémentant des entiers encodés en binaire).
Recherche positionnelle : Des mécanismes d'attention dure (approchés via un softmax à haute température) effectuent des recherches positionnelles exactes sur l'historique du ruban et l'entrée originale en faisant correspondre des vecteurs clé-requête binaires.

2. Architecture A : WCM21 (basée sur Transformer)

Basée sur la construction de Wei, Chen et Ma (2021), il s'agit d'un transformateur encodeur-décodeur :

Encodeur : Stocke le ruban initial sous forme d'une matrice fixe avec des encodages one-hot des symboles et des indices de position binaires.
Décodeur : Suit régressivement l'historique du calcul. Chaque étape implique un pipeline de :
1. Transition : Une couche feedforward implémentant la fonction de transition de la MT via FND.
2. Arithmétique : Une chaîne d'additionneurs à propagation de retenue met à jour la position de la tête.
3. Récupération de l'historique : Des couches d'attention auto-référentielle effectuent une recherche binaire dans l'historique du décodeur pour trouver la dernière écriture à la position actuelle de la tête.
4. Récupération du ruban : Une attention croisée lit le symbole du ruban original depuis l'encodeur.
5. Assemblage des symboles : Une couche feedforward basée sur la priorité sélectionne le symbole correct (dernière écriture > ruban original > vide).
Précision : Utilise un encodage de position binaire pour éviter les égalités fractionnaires dans les scores d'attention, permettant une implémentation avec une précision finie (float32).

3. Architecture B : SS95 (basée sur récurrent)

Basée sur Siegelmann et Sontag (1995), cette approche reformule la MT comme une machine à pile :

Encodage : Les piles sont encodées comme des nombres rationnels uniques au sein d'un ensemble de Cantor (en utilisant la base $b=4$ et le paramètre $\rho=1/2$ ).
Opérations : Les opérations de pile (pousser, retirer, regarder) sont réalisées comme des fonctions linéaires ou linéaires par morceaux de la valeur encodée, manipulées via des multiplications matricielles et des activations linéaires saturées ( $\sigma(x) = \text{clamp}(x, 0, 1)$ ).
Implémentation : Deux versions sont fournies :
- Une version explicite à pipeline de 4 couches.
- Une version récurrente « temps réel » à 1 couche.
Précision : La variante à 1 couche est sensible aux erreurs d'arrondi (amplifiées par la base $b$ ), nécessitant le float64 et limitant le nombre d'opérations fiables par rapport à la variante à 4 couches.

Contributions clés

Exposition constructive : Une dérivation systématique de la manière dont les réseaux ReLU réalisent des circuits booléens, progressant des portes individuelles aux formules FND et aux additionneurs binaires.
Implémentation exécutable : Un package PyTorch complet qui prend une description de MT et produit un modèle dont les poids sont spécifiés directement à partir de la définition de la machine. Aucun entraînement n'est requis ; le réseau est « correct par construction ».
Fondation open-source : Le code sert de référence pour étudier la stabilité des solutions construites sous perturbation et affinage par gradient, comblant le fossé entre l'existence théorique et l'optimisation pratique.

Résultats et capacités

Le package simule avec succès des machines de Turing, démontré via un vérificateur de parenthèses équilibrées.

WCM21 : Pour une machine avec 6 états, 5 symboles et 100 étapes, le modèle a une largeur d'embedding de 59. Il opère avec une exactitude numérique en float32, car toutes les valeurs intermédiaires restent dans $\{0, 1\}$ .
SS95 : La version à 4 couches est stable pour des entrées typiques. La version à 1 couche, bien que plus proche de la construction théorique originale, présente une dégradation de la précision après environ 8 opérations de retrait en raison de l'accumulation d'erreurs d'arrondi dans l'encodage de Cantor.

Importance et revendications

L'article se positionne non pas comme une proposition de nouvelles applications ou une revendication de performance supérieure par rapport aux modèles entraînés, mais comme un outil fondamental pour l'interprétabilité et la vérification théorique.

Interprétabilité par construction : Contrairement aux réseaux entraînés par descente de gradient, où les neurones peuvent être permutés ou entrelacés, chaque poids de ces réseaux construits a un but connu et interprétable (par exemple, une porte spécifique, un bit spécifique de l'additionneur).
Pont entre théorie et pratique : Ce travail comble le fossé entre les preuves abstraites de la complétude Turing et le code exécutable, fournissant une référence concrète pour le « pont symbolique-neuronal ».
Utilité future : Les auteurs suggèrent que les modèles servent d'initialisations pour étudier le paysage de perte autour des solutions construites, en investiguant spécifiquement la quantité de perturbation des poids que la simulation peut tolérer et si l'affinage produit des raccourcis manqués par la construction générale.

L'article conclut que, bien que ces constructions soient théoriquement solides et pratiquement exécutables, elles mettent en évidence les compromis inhérents entre la complétude Turing théorique et la stabilité numérique pratique, en particulier dans le contexte de l'arithmétique à précision finie.