Existe-t-il un lien caché entre l'existence d'ensembles innombrables et l'indécidabilité du problème d'arrêt?

Étant donné que les deux preuves utilisent l'argument diagonal, je me demande s'il existe un lien obscur entre l'existence d'ensembles infinis innombrables et l'indécidabilité du problème d'arrêt. Le problème d'arrêt serait-il décidable si tous les ensembles étaient dénombrables?

halting-problem Lenar Hoyt
la source

Oui, l'argument diagonal!

Mahdi Cheraghchi

@MCH Ma pensée était qu'il existe peut-être une caractérisation différente en plus de l'argument diagonal qui relie les deux. Cette question est peut-être trop floue pour SE.

Lenar Hoyt

Cela peut être un lien partiel: clairement, l'ensemble de toutes les langues sur un alphabet donné est indénombrable. Cependant, l'ensemble de toutes les machines Turing est dénombrable. Cela implique directement l'existence de problèmes indécidables. Cependant, ce raisonnement n'implique rien sur le problème de l'arrêt.

042

Il existe certainement des modèles théoriques des ensembles de ZFC où tous les ensembles sont dénombrables (mais pas dans le modèle), mais le problème d'arrêt est toujours indécidable. Voir cette question MathOverflow .

Peter Shor

S'il vous plaît, s'il vous plaît, dites indécidabilité à partir de maintenant.

Vijay D

Réponses:

Ce n'est pas un lien caché, mais un lien qui a été rendu explicite en utilisant le langage de la théorie des catégories et aussi une question très naturelle à poser et à étudier. Il y a pas mal de matériel sur le sujet.

CS Theory question demandant la même chose
Article de blog d'Andrej Bauer sur les théorèmes du point fixe et le théorème de Cantor.
A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points , Noson Yanofsky, 2003. Vous donne une introduction douce à l'article de Lawvere, ci-dessous.
Arguments diagonaux et catégories fermées cartésiennes , F. William Lawvere, 2006 republication d'un article de 1969 rendant ces connexions précises.
Incomplétude dans un cadre général , John Bell, 2007
De Lawvere à Brandenburger-Keisler: formes interactives de diagonalisation et d'auto-référence , Samson Abramsky et Jonathan Zvesper, 2010. Extension des arguments de Lawvere aux résultats d'impossibilité théorique du jeu.

Vijay D
la source