Quelle est la pertinence du calculable lors de l'application de la diagonallisation?

Question

Lorsque vous réfléchissez à la diagonalisation, j'ai toujours brillé sur le fait que l'énumération ou non la diagonale est calculable ou non.Quand est-ce important?

Dites par exemple, qui ont une énumération des nombres rationnels dans un ordre incutable, nous devrons alors supposer que soit une énumération insuffisante des rationnels n'existe pas, ni la diagonale donne un nombre insuffisant?

ou supposons que nous ayons une énumération d'un ensemble dénombrable mais non récursif.La diagonalisation produirait-elle un nombre insuffisant?

ou si nous supposons que nous avons une énumération calculable des nombres réels calculables, et nous devons faire une diagonalisation dessus, nous devrions alors supposer que le nombre de diagonales est insuffisant?Quelque chose ne semble pas ici.

En général, quelles sont les captures lors de la diagonalisation relatif à la calculabilité?

Answer 1

Il n'y a pas de captures. La diagonalisation est une technique de preuve très générale qui fonctionne dans un cadre classique, constructif et calculable. Il est utilisé pour prouver:

• qu'il n'y a pas d'étanchéité d'un ensemble à son Powerset
• que les chiffres réels ne peuvent pas être énumérés
• que les numéros réels calculables ne peuvent pas être énumérablement énumérées
• que l'oracle arrêté n'existe pas
• etc.

Dans sa forme la plus générale, il est connu sous le nom de Théorème à point fixe de Lawvere .

Vous demandez ce qui se passe si vous diagonalisez contre les nombres rationnels. Vous n'avez pas spécifié de quelle forme les rationnelles sont données, je suppose que vous voulez dire leurs expansions décimales. La diagonalisation produira un nombre réel qui n'est pas membre de l'énumération (ce réel peut être rationnel ou irrationnel, en fonction de la dénombrement que vous avez commencé). Si vous commencez par une énumération non calculable, le résultat peut être non calculable. Si vous commencez par une énumération calculable, vous obtiendrez un résultat calculable, car la diagonalisation préserve la calculabilité.

De même, si vous prenez une énumération calculable de nombres réels calculables (indiqués comme des séquences infinies de chiffres), le résultat d'une diagonalisation sera un nombre réel calculable qui n'est pas membre de l'énumération de départ.

Answer 2

Je ne suis pas sûr de savoir comment répondre à la question générale, mais pour les spécifiques:

Dites par exemple, qui ont une énumération des nombres rationnels dans un ordre incutable, nous devrons alors supposer que soit une énumération insuffisante des rationnels n'existe pas, ni la diagonale donne un nombre insuffisant?

Pourquoi pas seulement un nombre irrationnel?

ou supposons que nous ayons une énumération d'un ensemble dénombrable mais non récursif.La diagonalisation produirait-elle un nombre insuffisant?

pour l'ensemble de tous les nombres calculables oui.

ou si nous supposons que nous avons une énumération calculable des nombres réels calculables et que nous faisons la diagonalisation dessus, nous devrons supposer que le nombre de diagonales est insuffisant?

Il est clairement calculable, prouvant ainsi que vous ne pouvez pas avoir une énumération calculable de tous les nombres réels calculables.