# lo.logic – Uncomputability of a function based on the Busy Beaver function

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} 0quad {text{if}};{x_n};{text{is even}}{text{,}}\ 1quad {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?

Posted on Categories Articles