On sait qu'avec un ensemble dénombrable d'algorithmes (caractérisés par un nombre de Gödel), nous ne pouvons pas calculer (construire un algorithme binaire qui vérifie l'appartenance) tous les sous-ensembles de N.
Une preuve pourrait être résumée comme suit: si nous le pouvions, alors l'ensemble de tous les sous-ensembles de N serait dénombrable (nous pourrions associer à chaque sous-ensemble le numéro de Gödel de l'algorithme qui le calcule). Comme c'est faux, cela prouve le résultat.
C'est une preuve que j'aime car elle montre que le problème est équivalent aux sous-ensembles de N qui ne sont pas dénombrables.
Maintenant, je voudrais prouver que le problème d'arrêt n'est pas résolu en utilisant uniquement ce même résultat (dénombrabilité de N sous-ensembles), car je suppose que ce sont des problèmes très proches. Est-il possible de le prouver de cette façon?
Réponses:
Le théorème d'arrêt, le théorème de Cantor (le non-isomorphisme d'un ensemble et de son ensemble de puissance) et le théorème d'incomplétude de Goedel sont tous des exemples du théorème de Lawvere à point fixe, qui dit que pour toute catégorie fermée cartésienne, s'il existe une carte épimorphique puis tous les f : B → B a un point fixe.e : A → ( A ⇒ B ) F: B → B
Pour une belle introduction à ces idées, consultez cet article de blog d'Andrej Bauer .
la source