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".
Réponses
-
La proportion d'énoncés decidables tend vers 0, donc non.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Je sais, mais je ne vois pas en quoi ça permet de dire "donc non". J'ai bien précisé la proportion parmi les énoncés décidables de taille au plus n.
-
Ah pardon, j'ai lu trop vite et de mon téléphone (petit écran, presbytie). Mais de toute façon, ça ne change rien à cause de ta condition 1, la proportion tend vers 0 quand-même. Je te le laisse en exo ou pas? Je coupe la poire en 2:
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.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Hmmm je vois l'idée... Mais il pourrait exister un algorithme qui ne consiste pas à essayer toutes les démonstrations possibles non?
-
Non,non si tu as un tel algo tu obtiens immédiatement une fonction récursive totale qui borne toutes les preuves des énoncés que ta machine detecteAide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Ah bon, je vais y réfléchir. Et pour la question en remplaçant décidable par indécidable?
-
Bin, je ne sais pas, mais disons qu'il y a nettement plus de chances que ce soit possible qu'il y ait une proportion louable d'énoncés indécidables "connus" comme tels, ne serait-ce (peut-être pas de garantie) qu'en "elicutant" la preuve du gars qui prouve qu'ils sont en proportion 1Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 771 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 24
+15 Invités