💬 NLP

Turing or Cantor: That is the Question

Ce papier établit le rôle fondamental de Cantor dans les travaux de Turing, propose une mesure probabiliste de l'indécidabilité et une extension des machines d'Oracle, tout en définissant de nouvelles classes de complexité pour les problèmes indécidables (U-complete, D-complete, H-complete) et en y répondant négativement à une question analogue à P ≠ NP.

Auteurs originaux : Eugene Eberbach

Publié 2026-04-14

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Eugene Eberbach

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

🎩 Le Grand Débat : Qui est le vrai grand-père de l'informatique ?

Imaginez que l'informatique moderne est une immense cathédrale. Tout le monde s'accorde pour dire que Alan Turing (le père de l'ordinateur) en a posé les fondations et dessiné les plans. Mais cet article pose une question provocatrice : Georg Cantor, un mathématicien du 19ème siècle qui travaillait sur les infinis, ne serait-il pas le "grand-père oublié" qui a fourni les briques et le ciment sans lesquels la cathédrale ne pourrait même pas être construite ?

L'auteur dit : "Sans Cantor, Turing n'aurait rien pu prouver." C'est un peu comme si on disait que sans la théorie de la gravité de Newton, Einstein n'aurait jamais pu inventer la relativité.

🧩 Le Problème de la "Boîte Noire" (L'Entscheidungsproblem)

Au début du 20ème siècle, les mathématiciens pensaient qu'on pouvait créer un robot (un algorithme) capable de répondre à n'importe quelle question mathématique par "Vrai" ou "Faux". C'était le rêve de l'homme parfait.

Turing a dit : "Non, c'est impossible."
Il a prouvé qu'il existe des problèmes que même l'ordinateur le plus puissant ne pourra jamais résoudre.

L'analogie de la bibliothèque :
Imaginez une bibliothèque infinie contenant tous les livres possibles (toutes les combinaisons de lettres).

Cantor a dit : "Il y a plus de livres dans cette bibliothèque que de nombres entiers que vous pouvez compter." (L'infini des livres est plus grand que l'infini des nombres).
Turing a dit : "Je vais créer un catalogue (un ordinateur) pour lister tous les livres. Mais comme il y a plus de livres que de pages dans mon catalogue, je ne pourrai jamais tout lister. Il restera toujours des livres que mon catalogue ne peut pas trouver."

C'est ce qu'on appelle le problème de l'indécidabilité.

📏 Une nouvelle règle pour mesurer l'impossible

Jusqu'à présent, on disait d'un problème : "C'est impossible, point final." L'auteur propose une idée plus subtile : Mesurer à quel point un problème est impossible.

L'analogie de la plage :
Imaginez une plage où il y a des coquillages (les problèmes solubles) et des rochers (les problèmes insolubles).

Si vous avez 100% de rochers, c'est un problème 100% insoluble.
Si vous avez 90% de rochers et 10% de coquillages, c'est un problème 90% insoluble.
Si vous avez 0% de rochers, c'est un problème facile.

L'auteur suggère de classer les problèmes non pas seulement par "résoluble" ou "non résoluble", mais par le pourcentage de cas impossibles dans leurs données d'entrée. C'est comme dire : "Ce problème est dur, mais peut-être que 80% du temps, on peut trouver une réponse si on a de la chance avec les données d'entrée."

🏗️ Trois nouvelles catégories pour l'impossible

L'auteur propose de créer trois nouveaux "rayons" dans la bibliothèque des problèmes impossibles, inspirés par les travaux de Cantor sur les différents niveaux d'infini.

La classe U-Complete (Universelle) :
- C'est quoi ? Des problèmes où on peut trouver la réponse si elle est "Vrai", mais on ne sait jamais si c'est "Faux".
- L'analogie : C'est comme chercher un trésor. Si vous le trouvez, vous savez que vous avez gagné. Mais si vous ne le trouvez pas, vous ne savez pas s'il n'existe pas ou si vous avez juste mal cherché. C'est le niveau "le moins dur" de l'impossible.
La classe D-Complete (Diagonalisation) :
- C'est quoi ? Des problèmes encore plus tordus, où on ne peut même pas vérifier si une réponse est vraie ou fausse, même avec un temps infini.
- L'analogie : C'est comme essayer de lire un livre dont les pages changent de texte chaque fois que vous lisez une phrase. Vous ne pouvez jamais être sûr de rien. C'est le niveau "très dur".
La classe H-Complete (Hyper-computation) :
- C'est quoi ? Des problèmes qui défient même les machines les plus imaginables, ceux qui nécessitent des "oracles" (des boîtes magiques qui savent tout).
- L'analogie : C'est comme essayer de résoudre un puzzle dont les pièces n'existent pas encore dans l'univers. C'est le niveau "impossible absolu" pour nos ordinateurs actuels.

🚀 Pourquoi est-ce important aujourd'hui ?

Aujourd'hui, on parle beaucoup d'Intelligence Artificielle (IA) et de réseaux de neurones. L'auteur nous rappelle que Turing lui-même pensait que ses machines classiques (les ordinateurs actuels) n'étaient pas suffisantes pour tout faire. Il avait imaginé des machines plus puissantes (les "machines-oracles").

Le message final :
L'informatique a passé 80 ans à essayer de résoudre des problèmes "faciles" (ceux qu'on peut faire en quelques secondes). Mais l'auteur nous dit : "Regardez autour de vous ! La majorité des problèmes sont en fait impossibles à résoudre parfaitement. Au lieu de désespérer, apprenons à mesurer cette impossibilité et à créer de nouvelles machines pour les approcher."

En résumé, cet article nous invite à regarder l'infini non pas comme un mur, mais comme une échelle. Et pour grimper cette échelle, nous avons besoin de la sagesse de Cantor (qui a inventé les échelles) autant que de l'ingéniosité de Turing (qui a construit les premiers échelons).

Titre : Turing ou Cantor : Tel est le Question

Auteur : Eugene Eberbach (Rensselaer Polytechnic Institute)
Date : Avril 2026 (Prépublication arXiv)

1. Problématique et Contexte

L'article s'attaque à la limite fondamentale de l'informatique théorique : l'indécidabilité des problèmes. Bien qu'Alan Turing soit reconnu comme le père de l'informatique pour avoir formalisé la machine de Turing (TM) et prouvé l'indécidabilité du Entscheidungsproblem (problème de la décision) de Hilbert, l'auteur soutient que cette découverte repose entièrement sur les travaux antérieurs de Georg Cantor en théorie des ensembles.

Le problème central abordé est le suivant :

La théorie de la complexité classique se concentre sur les problèmes décidables (P, NP) ou indécidables (comme le problème de l'arrêt), mais manque de structure pour classifier les différents degrés d'indécidabilité au-delà de la simple dichotomie "décidable/indécidable".
L'hypothèse de l'auteur est que l'indécidabilité n'est pas un état binaire, mais qu'elle forme une hiérarchie infinie, inspirée par les hiérarchies de cardinalités de Cantor et les oracles de Turing.
L'article vise à redéfinir le paysage des problèmes indécidables en introduisant de nouvelles classes de complexité et en proposant une mesure quantitative de l'indécidabilité.

2. Méthodologie

L'auteur utilise une approche combinant l'histoire des idées mathématiques, la théorie de la calculabilité et la théorie de la complexité :

Réinterprétation historique et logique : L'article démontre que la preuve de Turing de l'indécidabilité du Entscheidungsproblem est une application directe de l'argument diagonal de Cantor et de la différence de cardinalité entre les entiers (ensembles dénombrables, machines de Turing) et les réels (ensembles non dénombrables, problèmes/langages).
Nouvelle preuve de l'indécidabilité : L'auteur propose une preuve plus courte de l'indécidabilité du problème de l'arrêt de la Machine de Turing Universelle (UTM) en s'appuyant explicitement sur le théorème de Cantor concernant la puissance de l'ensemble des sous-ensembles.
Extension des modèles de calcul : L'article étend le concept de machine oracle de Turing (o-machine) pour englober toute la classe des modèles de calcul "super-Turing" (hypercalcul), incluant les machines à choix (c-machines) et les machines non organisées (u-machines).
Mesure probabiliste de l'indécidabilité : Une nouvelle méthodologie est proposée pour quantifier l'indécidabilité d'un problème en fonction de la distribution de probabilité de ses données d'entrée. L'indécidabilité est mesurée par le pourcentage d'instances d'entrée qui sont indécidables par rapport aux instances décidables.
Définition formelle de classes de complexité : Sur le modèle de la classe NP-complet (pour les problèmes intraitables), l'auteur définit formellement trois nouvelles classes pour les problèmes indécidables.

3. Contributions Clés

A. Réhabilitation du rôle de Cantor

L'article affirme que sans les travaux de Cantor sur les infinis dénombrables et non dénombrables, les résultats de Turing n'auraient pas été possibles. Cantor est présenté comme le "grand-père implicite" de l'informatique, ayant fourni les outils mathématiques (diagonalisation, cardinalité) essentiels pour prouver les limites de l'algorithmique.

B. Mesure de l'indécidabilité

L'auteur propose de ne plus voir un problème indécidable comme totalement insoluble, mais d'évaluer son "degré d'insolvabilité".

0% d'indécidabilité : Problèmes récursifs (décidables).
100% d'indécidabilité : Tous les cas d'entrée sont indécidables.
Mesure intermédiaire : Basée sur la distribution des entrées, permettant d'estimer quelles instances peuvent être résolues par des techniques randomisées ou d'approximation.

C. Introduction de trois nouvelles classes de complexité pour les problèmes indécidables

Inspirées par la classe NP-complet, trois classes sont définies pour catégoriser les problèmes indécidables selon leur difficulté croissante :

Classe U-complete (Universal Complete) :
- Définition : Langages semi-décidables (Récursivement Énumérables mais non Récursifs - REnonREC).
- Propriété : Les mots dans le langage peuvent être acceptés en un nombre fini d'étapes, mais les mots hors du langage peuvent nécessiter un nombre infini d'étapes (ne jamais s'arrêter).
- Exemples : Le langage de la Machine de Turing Universelle ( $L_u$ ), le Problème de Correspondance de Post (PCP), le problème du "Busy Beaver".
- Résultat clé : Prouvé que les langages récursifs ne sont pas égaux aux langages récursivement énumérables non récursifs pour cette classe.
Classe D-complete (Diagonalization Complete) :
- Définition : Langages non récursivement énumérables (non-RE).
- Propriété : Aucun mot (ni dans, ni hors du langage) ne peut être décidé en un nombre fini d'étapes par une machine de Turing standard.
- Exemples : Le langage de diagonalisation ( $L_d$ ), le complément du langage universel.
- Différence avec U-complete : Même si l'on connaît la solution, on ne peut pas la vérifier en temps fini.
Classe H-complete (Hypercomputation Complete) :
- Définition : Langages hyper-indécidables, nécessitant des ressources infinies (temps ou mémoire) même pour les modèles de calcul super-Turing.
- Propriété : Indécidabilité même avec un nombre infini d'étapes (nécessite une hiérarchie d'oracles ou des modèles d'hypercalcul).
- Exemple : Le langage d'hyper-diagonalisation ( $L_{hd}$ ).

D. Hiérarchie Infinie

L'article postule l'existence d'une hiérarchie infinie de classes de complexité pour les problèmes indécidables, directement inspirée de la hiérarchie des cardinaux infinis de Cantor ( $\aleph_0, \aleph_1, \dots$ ) et des systèmes logiques de Turing basés sur les ordinaux constructifs.

4. Résultats Principaux

Preuve simplifiée : Une démonstration plus concise de l'indécidabilité du Entscheidungsproblem est fournie, reposant uniquement sur la cardinalité des ensembles (Cantor) et l'autoréférence.
Réponse négative à une question analogue à P vs NP : Pour la classe U-complete, l'auteur démontre que la question de savoir si les langages récursifs sont égaux aux langages récursivement énumérables non récursifs a une réponse négative (ils ne sont pas égaux). Cela établit une séparation stricte dans le monde des problèmes indécidables, similaire à la séparation P vs NP mais pour des problèmes non résolubles.
Corollaire de cardinalité : Il existe strictement plus de problèmes indécidables (cardinalité des réels, $\mathfrak{c}$ ) que de problèmes décidables (cardinalité des entiers, $\aleph_0$ ).
Extension des modèles de calcul : La généralisation des machines oracle de Turing vers une classe complète de modèles hypercalculatoires est formalisée.

5. Signification et Impact

Changement de paradigme : L'article remet en cause la vision binaire traditionnelle (décidable/indécidable) en proposant une granularité fine de l'indécidabilité. Cela ouvre la voie à l'étude de problèmes "partiellement" indécidables ou à la résolution d'instances spécifiques via des approches probabilistes.
Fondements théoriques : En reliant explicitement Cantor à l'informatique moderne, l'article renforce les fondements mathématiques de la théorie de la calculabilité et justifie la nécessité de modèles de calcul au-delà de la machine de Turing classique (hypercalcul).
Implications pour l'IA et l'apprentissage automatique : L'auteur note que les algorithmes évolutionnaires et les réseaux de neurones (qui opèrent parfois sur des infinis ou des approximations) pourraient être vus comme des tentatives de résoudre des problèmes appartenant aux classes U, D ou H, dépassant ainsi les limites des algorithmes récursifs classiques.
Nouveaux outils d'analyse : La définition des classes U-complete, D-complete et H-complete offre un cadre pour classer la difficulté des problèmes non résolubles, similaire à la façon dont la classe NP-complet classe les problèmes difficiles mais résolubles.

En conclusion, cet article propose une refonte théorique majeure de la compréhension de l'indécidabilité, en intégrant les travaux de Cantor comme pilier central et en établissant une nouvelle taxonomie de complexité pour les problèmes que les ordinateurs classiques ne peuvent pas résoudre.