Incomputabilidad de una función basada en la función Busy Beaver

Question

Dejar $\log _b^ac$denotar una base iterada$b$función de logaritmo. Por ejemplo,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$

Elija un modelo arbitrario M de máquinas de Turing, asumiendo que una máquina opera con el alfabeto de dos símbolos:$0$ como el símbolo en blanco y $1$como el símbolo que no está en blanco. A estas máquinas las llamaremos "máquinas M".

Dejar $f(n)$ denotar el número máximo de símbolos que no están en blanco que pueden ocurrir en la cinta cuando una máquina M en particular se detiene, asumiendo que todas las máquinas comienzan con la entrada en blanco y la tabla de instrucciones contiene como máximo $n$ estados operativos.

Entonces la función $F(n)$ se define de la siguiente manera: $${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.$$ dónde $x_n$ es el número natural más pequeño tal que $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$

Pregunta: es la función $F(n)$ Incomputable para cualquier modelo M (es decir, no existe una máquina M que pueda calcular la $F(n)$función, no importa qué M elijamos)? Si es así (o no), ¿es posible probarlo?

EDITAR
Supongamos que elegimos un modelo descrito en la sección "El juego" del artículo de Wikipedia "Busy Beaver" . Es$F$Incomputable por tales máquinas? También estoy interesado en cómo probar esto.

Answer 1

El logaritmo anidado no hace mucho aquí. Es una función computable con un inverso computable y, por lo tanto, las funciones$n \mapsto x_n$ y $f$ no solo son equivalentes a Turing, sino que se relacionan mediante un reajuste computable.

Como tal, la respuesta a esta pregunta también se aplica aquí.

Ciertamente, podríamos configurar nuestras máquinas de Turing de manera que nunca escriban un número total de símbolos que no estén en blanco que caigan en un rango que haría $x_n$impar. Necesitaríamos hacer algunos cálculos paralelos para determinar los rangos aceptables, pero dado el tamaño de los rangos, espero que los símbolos que necesitamos para determinar el siguiente intervalo que podemos usar finalmente no nos saquen del intervalo.

Por otro lado, para una configuración natural, no veo ninguna razón por la que $F$alguna vez sería computable. Pero realmente probar esto para una configuración en particular requeriría pensar mucho más en los detalles de un modelo de máquina de Turing en particular de lo que me gustaría hacer.