🔢 mathematics

A Finite-State Proof of the Well-Definedness of a Perturbed Hofstadter Sequence

Cet article démontre que la séquence de Hofstadter perturbée définie par Q(1)=1, Q(2)=1 et Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))+(-1)^n est bien définie pour tout n≥1 en réduisant la récurrence infinie à un système de contraintes combinatoires finies vérifiable par analyse exhaustive.

Auteurs originaux : Marco Mantovanelli

Publié 2026-04-01

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Marco Mantovanelli

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 une suite de nombres comme une chaîne de dominos infinie. Pour faire tomber le domino numéro 100, vous devez savoir où sont tombés les dominos 99 et 98. Mais dans une suite très particulière appelée la suite de Hofstadter, c'est encore plus bizarre : pour faire tomber le domino 100, vous devez regarder le domino numéro $100 - (\text{valeur du domino 99})$ .

Le problème ? Si le domino 99 a une valeur très élevée, vous pourriez devoir regarder en arrière, avant le début de la chaîne. Si vous tombez sur un numéro négatif ou zéro, la chaîne s'arrête, le calcul devient impossible, et la suite est "cassée".

Depuis des décennies, les mathématiciens se demandent si la version originale de cette suite casse toujours ou non. Personne ne l'a encore prouvé.

Mais dans cet article, l'auteur, Marco Mantovanelli, s'intéresse à une version modifiée de cette suite (avec un petit "ajustement" mathématique : un signe qui change à chaque tour). Il prouve que, pour cette version-là, la chaîne de dominos ne cassera jamais. Elle continuera pour toujours.

Voici comment il y arrive, expliqué simplement :

1. Le problème : Une forêt trop grande à explorer

Penser à tous les nombres possibles (1, 2, 3... jusqu'à l'infini) est comme essayer de cartographier une forêt infinie. On ne peut pas vérifier chaque arbre un par un. La suite dépend de son propre passé de manière si complexe qu'il est impossible de prédire l'avenir avec une simple formule.

2. La solution : Réduire la forêt à un petit jardin

L'idée géniale de l'auteur est de dire : "Attendez, même si la forêt est infinie, la façon dont les arbres poussent les uns à côté des autres suit des règles très simples et répétitives."

Il ne regarde pas les nombres eux-mêmes (qui peuvent devenir gigantesques), mais l'ambiance autour d'eux.

Imaginez que vous ne regardez pas la hauteur exacte de chaque arbre, mais juste si l'arbre d'à côté est "grand", "petit", "très grand", ou s'il y a une "dette" (un petit déséquilibre causé par le signe qui change).
Il découvre qu'il n'existe que 28 types d'ambiances (ou "contextes") possibles dans cette forêt. C'est comme si, malgré l'infini, il n'y avait que 28 façons différentes de disposer les dominos les uns par rapport aux autres.

3. Le jeu de l'auto-stop (Le graphe de compatibilité)

Une fois qu'on a ces 28 ambiances, on se demande : "Si je suis dans l'ambiance A, quelle ambiance peut suivre ?"

L'auteur dessine une carte (un graphe) avec ces 28 points.
Il trace des flèches entre eux pour montrer quelles transitions sont autorisées.
C'est comme un jeu de l'où : si vous êtes sur la case "Ambiance 1", vous ne pouvez aller que sur la case "Ambiance 2" ou "Ambiance 5".

Le but est de voir si on peut faire un chemin infini sur cette carte sans jamais se bloquer.

4. La révélation : Deux mondes possibles

En analysant cette carte, l'auteur découvre quelque chose de surprenant : il n'y a pas de chaos total. Il existe seulement deux façons (deux "modes") de parcourir ce système :

Mode A : On commence avec une certaine ambiance de départ.
Mode B : On commence avec une autre.

Une fois que vous choisissez votre point de départ, tout le reste de la suite est presque déterminé. C'est comme si l'univers de cette suite ne pouvait exister que dans deux états de réalité différents.

5. Le cœur du problème : Le "Noyau Critique"

L'auteur se rend compte que si la suite va casser, ce ne sera pas n'importe où. Cela doit arriver dans un tout petit groupe de 4 ambiances spécifiques, qu'il appelle le "Noyau Critique".

Imaginez que vous essayez de construire une tour de cartes. Si elle va tomber, ce sera à cause de 4 cartes précises au milieu. Si vous prouvez que ces 4 cartes peuvent tenir ensemble, alors la tour entière (l'infini) tiendra.

6. La preuve finale : Le dénombrement

Puisque le "Noyau Critique" n'a que 4 éléments, l'auteur peut faire ce que les mathématiciens appellent une vérification exhaustive.

Il prend tous les sous-groupes possibles de ces 4 cartes (il y en a 15).
Il vérifie, un par un, si l'on peut les assembler sans erreur.
Résultat : Pour chaque combinaison, il trouve une solution qui fonctionne. Il montre même qu'en choisissant simplement le "Mode A", tout fonctionne parfaitement.

Conclusion

En résumé, l'auteur a transformé un problème infini et effrayant (une suite qui pourrait casser à tout moment) en un petit puzzle fini et gérable (un jeu de 28 pièces avec 4 pièces critiques).

Il a prouvé que ce puzzle a une solution. Donc, la suite de Hofstadter perturbée ne cassera jamais. Elle est bien définie pour toujours.

C'est comme si on avait peur qu'un pont infini s'effondre, et qu'un ingénieur nous ait dit : "Ne vous inquiétez pas, j'ai analysé la structure. Il n'y a que 4 points faibles possibles. J'ai vérifié ces 4 points, ils sont solides. Le pont tiendra éternellement."

1. Problématique et Contexte

L'article s'intéresse à la définition globale (well-definedness) d'une classe de suites récurrentes non locales appelées suites de type Hofstadter.
Le problème central est de déterminer si une suite définie par récurrence produit une valeur pour tout entier $n \ge 1$ , ce qui équivaut à vérifier que tous les arguments de la récursion restent strictement positifs au cours de l'évolution.

Le cas classique : La suite $Q$ de Hofstadter, définie par $Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))$ , est célèbre pour son comportement complexe. La question de savoir si elle est bien définie pour tout $n$ reste un problème ouvert et notoirement difficile.
Le modèle perturbé : L'auteur étudie une variante perturbée introduite précédemment :
$Q(1) = 1, \quad Q(2) = 1$
$Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)) + (-1)^n$
Le terme $(-1)^n$ introduit une perturbation alternée. Bien que cela semble mineur, l'auteur démontre que cette perturbation crée une asymétrie structurelle permettant une analyse rigoureuse, contrairement au cas non perturbé.

2. Méthodologie : Réduction à un Système Fini

La preuve repose sur une idée centrale : remplacer la structure de récursion infinie par un modèle combinatoire fini. Au lieu de suivre les valeurs numériques (qui sont non bornées), l'auteur encode le comportement local de la récurrence en un nombre fini d'états symboliques.

La démarche se décompose en plusieurs étapes clés :

A. Encodage Symbolique et Contextes Locaux

Au lieu de travailler directement sur $Q(n)$ , l'auteur définit un ensemble fini d'états symboliques $S = \{S_0, \dots, S_7\}$ et un paramètre de "dette" $d \in \{0, 2\}$ (gérant la perturbation alternée).
Une contexte $\lambda$ est un tuple $(p, R, i, \pi, d)$ qui capture :

Un motif local $p$ des états symboliques.
Le régime de récurrence $R$ .
La position $i$ , la parité $\pi$ et la dette $d$ .
L'ensemble des contextes admissibles $\Lambda_{adm}$ est fini (28 éléments).

B. Le Graph de Compatibilité

La récurrence induit des contraintes de compatibilité entre les contextes voisins. Cela définit un graphe orienté $(\Lambda_{adm}, \Psi)$ où une arête $(\lambda, \mu)$ signifie que le contexte $\mu$ peut suivre $\lambda$ dans une configuration valide.

Ce graphe se décompose en deux composantes connexes (dette 0 et dette 2).
La question de la définition globale de la suite est équivalente à l'existence d'une affectation globale valide (un homomorphisme de graphe) respectant toutes les contraintes de $\Psi$ .

C. Structure en Deux Modes

Un résultat structurel majeur est la décomposition en deux modes (Théorème 3) :

Toute affectation valide appartient soit au Mode A, soit au Mode B.
Ce choix est déterminé uniquement par la valeur au contexte racine $\lambda_0$ (soit $S_1[0]$ pour le Mode A, soit $S_2[0]$ pour le Mode B).
Une fois le mode choisi, les valeurs possibles pour chaque contexte sont restreintes à des ensembles de support ( $\Sigma_A(\lambda)$ ou $\Sigma_B(\lambda)$ ) calculés par propagation de contraintes.

D. Réduction au "Cœur Critique"

L'analyse des obstructions (cas où une affectation locale ne peut pas être étendue globalement) montre que :

Les contextes "insensibles" (où les ensembles de support sont identiques dans les deux modes) ne peuvent pas bloquer la récurrence.
Toute obstruction minimale doit être contenue dans un sous-ensemble fini appelé cœur critique : $\Lambda_{crit} = \{\lambda_0, \lambda_2, \lambda_{14}, \lambda_{24}\}$ .
La structure du graphe sur ce cœur est acyclique et hiérarchique, centrée sur $\lambda_0$ .

3. Résultats Principaux

Théorème Principal

La suite perturbée de Hofstadter est bien définie pour tout entier $n \ge 1$ .
Cela signifie que pour tout $n$ , les arguments $n - Q(n-1)$ et $n - Q(n-2)$ sont strictement positifs, évitant ainsi toute rupture de la récursion.

Preuve par Vérification Finie

La preuve se conclut par une vérification exhaustive sur le cœur critique :

Il existe $2^4 - 1 = 15$ sous-ensembles non vides de $\Lambda_{crit}$ .
L'auteur vérifie (via un programme informatique) que pour chaque sous-ensemble, il existe une affectation valide (spécifiquement dans le Mode A, utilisant l'état constant $S_1[0]$ ).
Puisqu'aucun sous-ensemble du cœur critique n'est une obstruction, aucune obstruction n'existe dans le système entier.
Par le lemme de réduction, cela garantit la définition globale de la suite.

4. Contributions Clés

Résolution d'un problème ouvert : Première preuve de définition globale pour une variante de la suite de Hofstadter, là où le cas classique reste ouvert.
Méthode de réduction finie : Démonstration qu'une récurrence méta-Fibonacci non locale peut être décrite par un système d'états finis au niveau du comportement local.
Décomposition en modes : Identification d'une rigidité globale (structure en deux modes) qui simplifie considérablement l'espace des solutions.
Vérification assistée par ordinateur : La preuve repose sur une réduction mathématique rigoureuse suivie d'une vérification exhaustive de 15 cas sur un cœur de 4 éléments, rendue reproductible via un dépôt de code public.

5. Signification et Portée

Nouveauté théorique : L'article montre que la complexité apparente des suites de Hofstadter peut être maîtrisée par des méthodes de dynamique symbolique et de satisfaction de contraintes (CSP), même pour des définitions non locales.
Impact sur les suites méta-Fibonacci : Cela suggère que d'autres récurrences perturbées pourraient admettre des descriptions à états finis, ouvrant la voie à de nouvelles preuves de définition globale.
Rigueur et Reproductibilité : L'approche combine un argument mathématique structurel (réduction au cœur critique) avec une vérification computationnelle transparente. L'auteur note que la preuve est adaptée à une formalisation dans des assistants de preuve (comme Lean ou Coq).

En résumé, Mantovanelli démontre que la perturbation alternée $(-1)^n$ brise la complexité indécidable potentielle du cas classique en forçant la récurrence dans un cadre structurellement rigide et vérifiable, prouvant ainsi que la suite ne "casse" jamais.