Une variante de la fonction castor occupé

En lisant cette question « Problèmes naturels indécidables RE mais pas Turing-complete », le langage suivant m'est venu à l'esprit:

Si est la fonction de castor occupé (score maximum atteignable parmi toutes les machines de Turing à 2 symboles à arrêt n du type décrit ci-dessus, lorsqu'elles sont démarrées sur une bande vierge), définissez la fonction: $\Sigma(\cdot)$

B B (⟨ M ⟩) = {\begin{cases} 1 & ⟨ M ⟩ computes Σ (\cdot) \\ 0 & otherwise \end{cases}

$BB(\langle M \rangle) = \begin{cases} 1 & \text{$\langle M \rangle$ computes $\Sigma(\cdot)$}\\ 0 & \text{ otherwise} \end{cases}$

Définissez maintenant la langue:

$L = \{ \langle M \rangle \; | \; \langle M \rangle \mbox{ halts and } BB(\langle M \rangle) = 0 \}$

est-il récursivement énumérable? (il devrait être re: simulez simplement en parallèle M avec toutes les MT de même longueur, et si s'arrête et un autre s'arrête avec un score plus élevé, ajoutez M à l'énumération). $L$ $M$ $M'$

Pouvons-nous réduire le problème d'arrêt à ? (il semble qu'il ne puisse pas "capturer" l'arrêt des castors occupés) $L$

computability turing-machines Vor
la source

Estle nombre d'états?

| ⟨ M ⟩ |

$|\langle M \rangle|$

Pål GD

Quand allez-vous énumérer un qui ne s'arrête pas à ? ne peut pas être RE sauf si vous énumérez tous ses membres, et la procédure que vous avez décrite énumère uniquement ceux qui s'arrêtent réellement.

M

$M$

L

$L$

L

$L$

Steven Stadnicki

@ PålGD: oui c'est le nombre d'états (arrêt de l'état exclu)

Vor

@StevenStadnicki: J'ai implicitement supposé que ne contient que des machines qui s'arrêtent ... peut-être que je devrais le clarifier dans la question (laissez-moi y réfléchir un peu, peut-être que cela rend la question triviale).

L

$L$

Vor

@Kaveh Ce n'est même pas un problème de promesse - vous pouvez simplement définir (comme je pense que l'OP le voulait) comme .

L

$L$

L = {⟨ M ⟩ | M halts \land B B (⟨ M ⟩) = 0}

$L=\{\langle M\rangle | M\ \text{halts} \wedge BB(\langle M\rangle) = 0\}$

Steven Stadnicki

Réponses:

Je ne peux pas croire que je n'ai pas vu cela avant - mais oui, avec un oracle pour vous pouvez résoudre le problème d'arrêt. De toute évidence, un oracle pour nous donne «récursivement» toutes les machines d'arrêt de Castor non occupé, donc la question est «pouvons-nous comprendre récursivement dans ce que sont les castors occupés?». Définissez comme la fonction de comptage du «deuxième castor le plus occupé»; c'est-à-dire, le deuxième score atteignable le plus élevé parmi tous les TM à deux symboles d'arrêt à symboles. L'astuce ici est qu'il existe une fonction récursive telle que (il est presque certain que $L$ $L$ $L$ $\Sigma_2(n)$ $n$ $f()$ $\Sigma(n)\leq\Sigma_2(f(n))$ $f(n)=n+1$ fera l'affaire, en fait, mais cela nécessite de savoir que la fonction BB est strictement croissante): étant donné une machine de taille qui imprime 1s sur sa bande puis s'arrête, il y a quelques et deux machines de taille chacune qui impriment exactement 1s et exactement 1s, respectivement, sur leurs bandes - et cela vaut pour une machine 'castor occupé' même si nous ne sais pas explicitement . Cela signifie que le fait d'avoir une borne sur la fonction «deuxième castor occupé» pour donne une borne pour la fonction de castor occupé sur $M$ $n$ $\Sigma(M)$ $c\gt 1$ $\leq cn$ $\Sigma(M)$ $\Sigma(M)+1$ $M$ $M$ $f(n)$ $n$ ; mais en ayant cela, il est facile de résoudre le problème d'arrêt pour un TM de taille - si alors dites que s'arrête; sinon, trouvez la machine la plus longue de taille dans (ce qui peut être fait récursivement car il n'y a qu'un nombre fini de machines de taille ) et simulez pour autant d'étapes que cette machine prend pour arrêt. Si ne s'arrête pas dans ce délai, ne peut pas s'arrêter. $M$ $n$ $\langle M\rangle\in L$ $M$ $f(n)$ $L$ $\leq f(n)$ $M$ $M$ $M$

Steven Stadnicki
la source

Merci; inspiré par votre réponse, j'ai trouvé un rapide (trivial) -: réduction directe du problème d'arrêt dans une réponse séparée.

Vor

Il s'agit d'une version retravaillée de la bonne réponse de Steven, avec une réduction explicite du problème Halting.

Étant donné construire qui exécute sur et s'il s'arrête va à droite de la bande, écrit un 0 et s'arrête. $\langle M \rangle, w$ $M'$ $M$ $w$

Si s'arrête, car il existe un TM équivalent de la même taille qui écrit un 1 et s'arrête; nous pouvons donc utiliser le décideur pour pour vérifier si s'arrête sur ( s'arrête sur ssi ) $M'$ $BB(M')=0$ $L$ $M$ $w$ $M$ $w$ $M' \in L$

... il s'est avéré que la question est en effet triviale :-)

Vor
la source