[Hommage→Distillation] Richard E. Stearns (1936-2026) — co-fondateur de la théorie de la complexité (Turing 1993) : 6 résonances dans le dépôt, dont Arrow et les jeux répétés #15949

Contexte — l'hommage

Richard Edwin Stearns est décédé le 29 août 2026 à Ann Arbor (Michigan), à 90 ans.

Co-lauréat avec Juris Hartmanis du prix Turing 1993, « in recognition of their seminal paper which established the foundations for the field of computational complexity theory ». Leur papier — Hartmanis & Stearns, « On the computational complexity of algorithms », Trans. Amer. Math. Soc. 117 (1965), 285–306 — écrit dans un laboratoire industriel (GE Schenectady) pour un champ qui n'avait pas encore de nom, lui a donné son nom.

Quatre lauréats Turing ont dit de ce papier :

• Cook (1982) : « This paper was widely read and gave the field its title. »
• Karp (1985) : « it is the 1965 paper by Juris Hartmanis and Richard Stearns that marks the beginning of the modern era of complexity theory. »
• Hopcroft (1986) : « Turing's work might have remained in the realm of mathematics and logic were it not for a seminal paper […] by mathematicians Hartmanis and Stearns. »
• Ullman (2020) : « both amazingly insightful and widely useful. »

Sources vérifiées firsthand : CACM In Memoriam (Spafford & Garfinkel, 03/09/2026) et Computational Complexity blog (Gasarch, 04/09/2026).

Pourquoi un hommage plus large que Munkres

Demande Emerjesse (13/09) : « encore plus que pour Munkres, ça mérite une issue de distillation hommage ». Le précédent est la série Munkres 1/3–3/3 (#12598, #12599, #12600 + lake assignment_lean) — un hommage par l'œuvre, où l'hommage est un prétexte pédagogique et non une notice biographique.

La différence de calibre est objective : Munkres était co-éponyme d'un algorithme (Kuhn-Munkres) touchant une série (GameTheory). Stearns est un fondateur de discipline dont l'œuvre tache au moins six domaines déjà présents dans le dépôt — dont deux résonances inattendues et très fortes (§ Résonances 5 et 6).

L'œuvre et ses résonances dans CoursIA — vérifié firsthand

1. Hiérarchie de Hartmanis–Stearns (1965) — le cœur

Plus de temps (ou de mémoire) ⟹ strictement plus de problèmes résolubles ; la hiérarchie est infinie. Posé le concept de classe de complexité sur machine de Turing multitête.

Résonance : c'est le GAP principal. Aucune série CoursIA ne couvre la théorie de la complexité computationnelle (recherche code : hierarchy theorem, P vs NP, complexity class → 0 notebook dédié). C'est un fondement de l'informatique qui manque au dépôt — et l'hommage est l'occasion naturelle de le combler.

2. Langages formels, automates, parsing

• Stearns & Lewis : syntax-directed transduction et les parseurs LL(k) — « usually the first parsing method students meet ».
• Stearns (1967) : A regularity test for pushdown machines — si un langage régulier a un DPDA de taille n, il a un DFA de taille ≤ n^(n^(n^O(n))) (blow-up sur-exponentiel mais calculable ; amélioré par Valiant en 2^(2^O(n))).
• Stearns a aussi montré que les langages hors-contexte se reconnaissent en espace O(log² n), et établi la hiérarchie en espace.

Résonances dépôt : SymbolicAI/SymbolicLearning/SL-10-ActiveAutomataLearning.ipynb, Sudoku/Sudoku-13-SymbolicAutomata-Python.ipynb, slides/09-traitement-automatique-langues/. Le thème automates + complexité du parsing est présent, mais sans le théorème qui en fonde la hiérarchie.

3. Analyse de pire cas des heuristiques TSP

Stearns a produit la première analyse systématique de pire cas des heuristiques du voyageur de commerce — motivée par des problèmes industriels GE (perçage de tôles).

Résonances dépôt : Search/Applications/Hybrid/App-13b-TSP-Metaheuristics-CSharp.ipynb, App-17b-VRP-Logistics-Python.ipynb. Angle pédagogique fort : le notebook optimise des heuristiques ; Stearns est celui qui a posé « quelle garantie de pire cas donne cette heuristique ? ».

4. Complexité structurelle et mémoire (avec Hartmanis, Lewis)

Étude pionnière des relations entre temps et espace, machines à accès borné, hiérarchies de ressources. Travaux fondateurs sur la structure des classes.

5. ⭐ Résonance inattendue — le paradoxe d'Arrow

Le tout premier papier de Stearns (étudiant à Carleton College) portait sur le paradoxe d'Arrow, publié dans The American Mathematical Monthly en 1959.

Or CoursIA possède une série SocialChoice complète : GameTheory/SocialChoice/01-Arrow-Impossibility-Theorem.ipynb, game_theory_lean/SocialChoice/Arrow.lean (+ _en), examples/arrow_simple.lean, twin-pair socialchoice-1-arrow-impossibility.yaml.

Angle pédagogique : l'homme qui a fondé la théorie de la complexité a commencé par le théorème d'impossibilité d'Arrow. Relier SocialChoice à un destin scientifique est exactement le registre d'un hommage.

6. ⭐ Résonance inattendue — jeux répétés à information incomplète

Stearns a travaillé à l'Arms Control and Disarmament Agency sur les jeux répétés à information incomplète ; ce travail devint un chapitre du livre d'Aumann & Maschler (1995) (prix Lanchester), dont la page de titre porte « with the collaboration of Richard E. Stearns ». Il se qualifiait de « semi-auteur » et appelait l'épisode « the story of how I almost won the Lanchester Prize ».

Or CoursIA possède GameTheory/repeated_games_lean/ (lake complet : README FR/EN, STATUS.md, lakefile) et game_theory_lean/RepeatedGames.lean (+ _en), ainsi que la série ICT (ICT-13-AxelrodStrategicMorphodynamics) sur la coopération itérée.

Angle pédagogique : le pont entre jeux répétés et contrôle des armements — la théorie des jeux comme outil de paix — est un grain réflexif rare et précieux.

7. Autres fils (mention, pas cœur)

• Partition pairs et minimisation d'états de machines séquentielles (premier papier conjoint avec Hartmanis, 1961).
• Rétrospective de 1965 sur la théorie de l'information de Shannon comme moteur du questionnement fondateur (« he thought there must be a reason why things are hard »).

Proposition — série d'hommage « 1/3 → 3/3 », gabarit Munkres

⚠️ Ceci est une proposition d'opportunité, pas un mandat d'implémentation. Le patron Munkres a couvert l'œuvre en 3 volets + lake Lean. Ici l'œuvre est plus vaste : proposer un découpage, ou argumenter un format différent (issue unique + notebooks, sans lake).

Volet 1/3 — le fondement : la hiérarchie (avec gap comblé)
Nouveau grain (série à décider : SymbolicAI ? nouveau Complexity/ ?) sur la hiérarchie de Hartmanis–Stearns : classes de complexité, machine de Turing multitête, théorème diagonal de la hiérarchie, simulation. Adossé à un lake Lean (complexity_lean ?) dans la lignée des lakes existants (discrepancy_lean, assignment_lean, repeated_games_lean). Honnêteté requise : Mathlib a-t-il de quoi formaliser les machines de Turing et la diagonalisation ? À vérifier firsthand — même méthode que l'analyse #15944 (lister nommément l'étage absent).

Volet 2/3 — le Stearns inattendu : Arrow + jeux répétés
Rattachement de SocialChoice/Arrow et de repeated_games_lean à Stearns (encarts hommage + renvois croisés). Résonances 5 et 6 ci-dessus — c'est le volet le plus original.

Volet 3/3 — automates, parsing, TSP : la complexité appliquée
LL(k) et transduction dans SL-10-ActiveAutomataLearning ; le test de régularité de DPDA ; l'analyse de pire cas des heuristiques dans App-13b-TSP-Metaheuristics. Résonances 2 et 3.

Question ouverte posée par cet hommage

L'hommage Munkres a produit un lake Lean. Pour Stearns, la formalisation naturelle serait celle des machines de Turing et de la hiérarchie — or c'est précisément un objet dont la disponibilité Mathlib est incertaine. Décider : l'hommage doit-il porter un lake (et lequel), ou un hommage purement pédagogique serait-il plus honnête ? Ne pas promettre un lake dont on n'a pas vérifié la faisabilité.

Précautions

• Personne décédée, sujet sensible : l'hommage est factuel et digne, jamais grandiloquent. Citer les sources (CACM, blog Gasarch) pour les faits biographiques.
• Ne pas dupliquer : aucune issue Stearns existante (vérifié : recherche Stearns sur le dépôt → 0 résultat pertinent ; les hits fix(Lean-14b): align pillar names with #2155 mandate #2637/enrich(Lean-14b): coherence audit - sorry counts + CPU attribution + theorem mapping #2373/enrich(Lean): pillar tables + RLE size demo + sorry roadmap for Lean-14b (See #2155) #2577/[Epic Conway] NB2 - Serie Game of Life : etoffer + s'appuyer sur le .lean reel #2155/[EPIC] Formalisations Lean : Conway (profondeur), Grothendieck, integration GameTheory + 3 exercices #2162 sont des faux positifs lexicaux).
• Vérifier les droits : les citations de Cook/Karp/Hopcroft/Ullman sont sourcées CACM — usage pédagogique documenté, citation exacte.
• Ne pas confondre avec les Turing 1993 co-lauréats ou d'autres disparitions récentes (Munkres feat(gametheory): hommage James Munkres (1930-2026) 1/3 — lake assignment_lean (Kuhn-Munkres) + notebook #12598 ; voir aussi la veille aicpp [Veille→Distillation] aicpp dsl_engine — synthèse symbolique déterministe guidée par LLM (ARC-AGI 57,5% training) : résonance Planners-04-NeuroSymbolic + SymbolicLearning, benchmark ARC manquant #13104).

Issue ouverte par Hermes (myia-po-2026) sur demande Emerjesse, 13/09/2026. Faits biographiques vérifiés firsthand (CACM + blog Computational Complexity). Résonances dépôt vérifiées firsthand par inspection de l'arbre et recherche code (SocialChoice/Arrow, repeated_games_lean, SymbolicLearning/SL-10, Search/Applications App-13b/App-17b, slides/09). Absence de couverture complexité vérifiée par recherche code.