Détecter les énoncés tordus?
Bonjour,
Existe-il une machine de Turing M prenant en entrée un énoncé de l'arithmétique de Péano, et vérifiant les conditions suivantes:
1. M termine sur toute entrée,
2. Si M renvoie "vrai" alors l'énoncé passé en entrée est décidable dans AP,
3. La proportion d'énoncés détectés par M parmi les énoncés décidables de taille au plus $n$ ne tend pas vers zéro quand $n$ tend vers l'infini.
On peut poser la même question en remplaçant "décidable" par "indécidable".
Existe-il une machine de Turing M prenant en entrée un énoncé de l'arithmétique de Péano, et vérifiant les conditions suivantes:
1. M termine sur toute entrée,
2. Si M renvoie "vrai" alors l'énoncé passé en entrée est décidable dans AP,
3. La proportion d'énoncés détectés par M parmi les énoncés décidables de taille au plus $n$ ne tend pas vers zéro quand $n$ tend vers l'infini.
On peut poser la même question en remplaçant "décidable" par "indécidable".
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ton 1 fait que ta machine va uniformément borner la longueur au delà de laquelle elle s'arrête pour éviter de ne jamais terminer, et la proportion des énoncés décidables qui demanderaient d'essayer plus longtemps et tester des textes plus longs tend vers 1, dès lors que tu admets que les décidables forment une part nulle. Evidemment, ce n'est pas une Lapalissade, mais presque, je te laisse combler la petite partie que je ne te formalise pas.