Considérez les problèmes de décision énoncés dans un langage formel «raisonnable». Disons des formules en arithmétique Peano d'ordre supérieur avec une variable libre comme cadre de référence, mais je suis également intéressé par d'autres modèles de calcul: équations diophantiennes, problèmes de mots issus de règles de réécriture utilisant des machines de Turing, etc. Une réponse exprimée dans n'importe quelle la formalisation classique serait bien, mais si vous savez à quel point le choix de la formalisation influence la réponse, ce serait également intéressant.
Compte tenu de la longueur de la déclaration d'un problème de décision, nous pouvons définir le nombre des états décidables de longueur et le nombre des états indécidables de longueur .D ( N ) N U ( N ) N
Que sait-on de la croissance relative de et ? En d'autres termes, si je prends au hasard un problème de décision bien formé, quelle est la probabilité qu'il soit décidable pour une longueur de déclaration donnée?D ( N )
Inspiré par cette question qui demande si «la plupart des problèmes et algorithmes [sont] décidables». Eh bien, si vous ne filtrez pas par intérêt, le sont-ils?
la source
Réponses:
la source