Let $\log \_b^ac$ denote an [iterated](https://en.wikipedia.org/wiki/Iterated_function) base-$b$ logarithm function. For example, $$\log \_2^3({2^{65536}}) = {\log \_2}({\log \_2}({\log \_2}({2^{65536}}))) = 4.$$


Pick an *arbitrary* model M of Turing machines, assuming that a machine operates with the two-symbol alphabet: $0$ as the blank symbol and $1$ as the non-blank symbol. We will call such machines “M-machines.”


Let $f(n)$ denote the maximum number of non-blank symbols which can occur at the tape when a particular M-machine halts, assuming that all machines start with the blank input and the table of instructions contains at most $n$ operational states.


Then the function $F(n)$ is defined as follows: $${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.$$ where $x\_n$ is the smallest natural number such that $$\log \_{{f}(n) + 2}^{x\_n}({f}(n + 1) + 3) < 2.$$


Question: is the function $F(n)$ uncomputable for any model M (that is, there does not exist an M-machine which can compute the $F(n)$ function, no matter which M we choose)? If yes (or no), is it possible to prove this?


**EDIT**  

Suppose that we pick a model described in the "The game" section in the ["Busy Beaver" Wikipedia article](https://en.m.wikipedia.org/wiki/Busy_beaver). Is $F$ uncomputable by such machines? I am also interested in how to prove this.



Uncomputability of a function based on the Busy Beaver function
The nested logarithm doesn't really do much here. It is a computable function with a computable inverse, and thus the functions $n \mapsto x\_n$ and $f$ are not only Turing equivalent, but related via computable rescaling.


As such, the answer to [this question](https://mathoverflow.net/questions/137421/busy-beaver-modulo-2?noredirect=1&lq=1) applies here, too.


We quite certainly could set up our Turing machines in a way that they never write a total number of non-blank symbols falling into a range that would make $x\_n$ odd. We'd need to do some side computations to figure out acceptable ranges, but given the size of the ranges I expect that the symbols we need to determine the next interval we can use will eventually not bring us out of the interval.


On the other hand, for a natural setup I see no reason why $F$ would ever be computable. But actually going proving this for a particular setup would require thinking much more about the details of a particular Turing machine model than I would want to do.


