Le problème de l'arrêt limité est décidable. Pourquoi ce conflit n'est-il pas avec le théorème de Rice?

Une déclaration du théorème de Rice est donnée à la page 35 de "Complexité computationnelle: une approche moderne" (Arora-Barak):

Une fonction partielle de $\{0,1\}^*$ à $\{0,1\}^*$ est une fonction qui n'est pas nécessairement définie sur toutes ses entrées. On dit qu'un TM $M$ calcule une fonction partielle $f$ si pour chaque $x$ sur lequel $f$ est défini, $M(x) = f(x)$ et pour chaque $x$ sur lequel $f$ n'est pas défini $M$ entre dans une boucle infinie lorsqu'il est exécuté en entrée . SiS f S α M α S S f $x$$S$est un ensemble de fonctions partielles, nous définissons être la fonction booléenne sur l' entrée sorties 1 ssi calcule une fonction partielle dans . Le théorème de Rice dit que pour tout non trivial , la fonction n'est pas calculable.$f_S$$\alpha$$M_\alpha$$S$$S$$f_S$

Wikipedia indique que les langages des machines de turing à temps limité sont EXPTIME complets. Je m'attends à ce que cette langue ressemble à accepte en moins de étapes . Soit donc un DTM qui décide de ce langage borné en temps exponentiel. Il semble que ce DTM décide d'une propriété pour TOUTES les machines de turing, donc mon intuition me dit que le théorème de Rice empêche une telle décision. Mais évidemment, calcule une fonction totale. x n } M $\{(\alpha,x,n) : M_\alpha$$x$$n$$\}$$M$$M$

Qu'est-ce qui me manque dans la relation entre ce langage et le théorème de Rice?

La langue

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

n'est pas un ensemble d'index, c'est-à-dire qu'il n'est pas de la forme

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

pour un certain ensemble de fonctions (récursives partielle) , avec la fonction (partielle) calculée par TM . Le théorème de Rice ne fait des déclarations que sur ces ; de nombreuses reformulations "intuitives" ne sont pas utiles. Voir aussi ici .$P$$f_M$$M$$L_P$

Notez que ce n'est pas seulement un détail technique ici. Le théorème de Rice ne s'applique pas à

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$ ,

Soit. Voyez-vous pourquoi?

Pour chaque machine , vous pouvez facilement construire de nombreuses machines qui acceptent la même langue , mais durer plus de étapes, et ne sont donc pas en . Ainsi, n'est pas un ensemble d'index.$L$$\langle M \rangle$$L$$L$

$L$ est décidable, en utilisant le même argument que pour la langue d'origine dont nous discutons.

Le théorème de Rice dit que vous ne pouvez rien dire sur le comportement ultime d'un programme lorsqu'il est exécuté à l'infini - peu importe la façon dont vous classifiez les programmes, il y aura deux programmes qui convergeront vers le même comportement ultime (fonction calculée ) bien que vous les ayez classés différemment.

Mais laisser les programmes s'exécuter à l'infini est essentiel. Pour savoir ce qu'ils font dans les premières étapes, vous pouvez simplement les simuler pour les n premières étapes, puis terminer de donner votre verdict sur la façon dont le programme s'est comporté. Une simulation similaire jusqu'à l'infini ne fonctionne pas, car si le programme simulé ne se termine jamais sur une entrée simulée, votre classificateur divergera également, au lieu de fournir une classification.$n$$n$

Tout d'abord, les mots dans votre langue ne sont pas des encodages de machines, ils contiennent plus d'informations, vous ne pouvez donc pas appliquer directement le théorème de Rice. Cela dit, le théorème de Rice parle de l'impossibilité de raisonner sur la fonction calculée par une machine de Turing (à savoir, si elle se trouve dans un ensemble ). Ce n'est pas le cas ici, car comme Raphaël l'a mentionné, il existe deux machines M , M ' qui calculent la même fonction, mais l'une réside dans votre langage et l'autre pas (ici j'ignore le problème syntaxique et j'oublie le fait que x , $S$$M,M'$$x,n$font partie de l'entrée). Le fait est que la propriété que vous regardez ici est mécanique et non sémantique (les machines peuvent calculer la même fonction, mais d'une manière différente).

Le théorème de Rice dit que, pour tout ensemble non trivial de langues, l'ensemble des machines de Turing qui reconnaissent une langue en  L est indécidable. Wikipedia dit qu'une langue spécifique est décidable. Il n'y a donc pas de contradiction.$\mathcal{L}$$\mathcal{L}$