Let $\log _b^ac$ denote an iterated 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. Is $F$ uncomputable by such machines? I am also interested in how to prove this.

operational statesis absolutely necessary. $\endgroup$ – lyrically wicked Jan 12 at 5:14examples ofmachine models, but do you have aprecise definitionof what constitutes a machine model? Both those cited usages areinformal(and in fact I suspect the first one is broader than you intend). $\endgroup$ – Noah Schweber Jan 12 at 5:262more comments