Incomputabilité d'une fonction basée sur la fonction Busy Beaver

Question

Laisser $\log _b^ac$désigner un itérée base-$b$fonction logarithme. Par example,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Choisissez un modèle arbitraire M de machines de Turing, en supposant qu'une machine fonctionne avec l'alphabet à deux symboles:$0$ comme symbole vierge et $1$comme symbole non vide. Nous appellerons ces machines des «M-machines».

Laisser $f(n)$ désignent le nombre maximal de symboles non vierges qui peuvent apparaître sur la bande lorsqu'une machine M particulière s'arrête, en supposant que toutes les machines commencent par l'entrée vierge et que le tableau d'instructions contient au plus $n$ états de fonctionnement.

Puis la fonction $F(n)$ est défini comme suit: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ où $x_n$ est le plus petit nombre naturel tel que $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Question: est la fonction $F(n)$ non calculable pour tout modèle M (c'est-à-dire qu'il n'existe pas de machine M capable de calculer le $F(n)$quelle que soit la fonction que nous choisissons)? Si oui (ou non), est-il possible de le prouver?

EDIT
Supposons que nous choisissions un modèle décrit dans la section "Le jeu " de l'article Wikipédia "Busy Beaver" . Est$F$non calculable par de telles machines? Je suis également intéressé par la manière de le prouver.

Answer 1

Le logarithme imbriqué ne fait pas grand chose ici. C'est une fonction calculable avec un inverse calculable, et donc les fonctions$n \mapsto x_n$ et $f$ ne sont pas seulement équivalents à Turing, mais liés via une redimensionnement calculable.

En tant que telle, la réponse à cette question s'applique ici aussi.

Nous pourrions certainement configurer nos machines de Turing de manière à ce qu'elles n'écrivent jamais un nombre total de symboles non vides tombant dans une plage qui ferait $x_n$impair. Nous aurions besoin de faire des calculs secondaires pour déterminer les plages acceptables, mais étant donné la taille des plages, je pense que les symboles dont nous avons besoin pour déterminer le prochain intervalle que nous pouvons utiliser ne nous sortiront pas de l'intervalle.

Par contre, pour une configuration naturelle, je ne vois aucune raison pour laquelle $F$serait jamais calculable. Mais en fait, prouver cela pour une configuration particulière nécessiterait de réfléchir beaucoup plus aux détails d'un modèle de machine de Turing particulier que je ne le souhaiterais.