Can all lengths of shortest non-halting inputs of all Turing machines be limited by the Busy Beaver applied to the corresponding numbers of states?

Question

Let $E_1$ denote the infinite enumerated collection of two-symbol (0 as blank symbol and 1 as non-blank symbol) one-tape (assuming that the tape is infinite in both directions) Turing machines: $${E_1} = \{ 1,\;\;2,\;\;3,\;\; \ldots \},$$

where each element is simply the index of the corresponding Turing machine. So, we can denote the $x$-th Turing machine by $\text{M}_x$.

The exact technical description of the design of these machines can be found in “The game” section in Wikipedia article about Busy beaver.

Let $G(x)$ denote the number of different states (not including the halting states!) of the corresponding $\text{M}_x$. It means that if there are $${(4n + 4)^{2n}}$$ $n$-state Turing machines, then $G(x) = 1$ if $1 \le x \le 64$, $G(x) = 2$ if $65 \le x \le 20736$ etc.

Let (0) denote an infinite sequence of consecutive blank symbols on the tape.

Let $T_1$ denote the configuration when a Turing machine starts in the state $A$ on an infinitely blank tape. Then $T_2$ denotes the configuration when a Turing machine starts in the state $A$ with its head positioned over the single 1 on the (0)1(0) tape; $T_3$ denotes the configuration when a Turing machine starts in the state $A$ with its head positioned over the leftmost 1 on the (0)11(0) tape; $T_4$ denotes the configuration when a Turing machine starts in the state $A$ with its head positioned over the leftmost 1 on the (0)111(0) tape, etc. That is, machines always start in the state $A$ so that the head at the start is positioned over the leftmost non-blank symbol of the tape, and the number of consecutive non-blank symbols on the tape increases by 1.

We define the following function: $F(x) = 0$ if $\text{M}_x$ halts on all configurations denoted by $T_y$ for any $y \ge 1$; otherwise, $F(x) = z$, where $z$ is the minimal positive number such that $\text{M}_x$ does not halt on the configuration denoted by $T_z$.

Let $S(x)$ denote the largest number of shifts made by any halting $x$-state 2-symbol Turing machine that starts from an infinitely blank tape. This definition is equal to the definition of “Maximum shifts function” given in Wikipedia article about Busy beaver: $$S(1) = 1,\;\;S(2) = 6,\;\;S(3) = 21,\;\;S(4) = 107,\;\; \ldots $$

Then $E_1$ corresponds to the following infinite sequence of integers:

$${E_2} = \left\{ {\left\lfloor {\frac{{F(1)}}{{S(G(1))}}} \right\rfloor ,\;\;\left\lfloor {\frac{{F(2)}}{{S(G(2))}}} \right\rfloor ,\;\;\left\lfloor {\frac{{F(3)}}{{S(G(3))}}} \right\rfloor ,\;\; \ldots } \right\},$$

where $\left\lfloor x \right\rfloor $ denotes a mathematical floor function.

Consider four possibilities:

Possibility 1: $E_2$ contains finitely many different integers and this amount is denoted by $Y$; then there exists the largest integer in $E_2$ and this integer is denoted by $Z$.

Question if Possibility 1 is true: is it possible to estimate a lower and upper bounds for $Y$ and $Z$?

Possibility 2: $E_2$ contains infinitely many different integers.

Question if Possibility 2 is true: is it possible to prove (or back up) this?

Possibility 3: $E_2$ contains all integers.

Question if Possibility 3 is true: is it possible to prove (or back up) this?

Possibility 4: $E_2$ contains infinitely many occurrences of any integer.

Question if Possibility 4 is true: is it possible to prove (or back up) this?

Answer 1

There exists a family of Turing machines $\{ \mathcal{T}_n : n \in \mathbb{N} \}$ such that:

• $\mathcal{T}_n$ has $k n$ states where $k$ is some fixed universal constant;
• $F(\mathcal{T}_n) \geq BB(BB(n))$.

Specifically, $\mathcal{T}_n$ simulates the $n$-state Busy Beaver in the left half of the tape, keeping track of the number of simulated iterations. Then, upon halting, it has the number $BB(n)$ in a register.

The machine proceeds to simultaneously simulate (via dovetailing) all Turing machines with at most $BB(n)$ states. If and when the $x$th simulated machine halts at time $y$, the Turing machine checks whether the $y$th input bit is a $0$ or a $1$. If it is a $0$, $\mathcal{T}_n$ halts. If it is a $1$, it continues running.

To prevent $T_n$ from halting, it is thus necessary to have $1$ bits in all positions corresponding to halting times of all machines of $\leq BB(n)$ states; consequently, there must be a $1$ in position $BB(BB(n))$ on the input tape.

Answer 2

I do not know whether the more qualified members here consider this question suitable for this site, but anyway here is a partial answer to your question (this a bit too long for a comment anyway). I think the set $E_2$ must contain an infinite number of elements.

Here is my reasoning. Let's first notice that the configurations you have written as $T_x$ correspond to giving an input $x-1$ to the machine. The first thing we can observe is that given a program with access to the function $F$ (defined in your original question) one can calculate the characteristic set corresponding to the set TOTAL. TOTAL being the set containing indexes of all (ordinary) programs that halt on every input. Similarly, given a program with access to the characteristic function of TOTAL one can compute the function $F$ (just observe that $H \le_T TOTAL$). Both of these reductions are relatively clear.

Now, it seems to me, the question we should ask is whether the function $F$ is $H$-computably bounded, where $H$ is the halt set. I think the answer should be in negative. Here is the reason. Suppose, by contradiction, that $F$ is indeed $H$-computably bounded by some function $F_B$. Then we can actually show that characteristic function of TOTAL is $H$-computable, or in other words $TOTAL \le_T H$ (which is indeed well-known to be false). To see this, suppose we have an enumeration of all ordinary programs (without access to any oracale). Consider any program with index $i$. We can simply use the halt oracle to check the halting of the given program for all inputs from $0$ to $F_B(i)$. Here $F_B$ is a function such that $F_B(x) > F(x)$ for all $x$. If the program loops on even just one of the given inputs, then we return 0/false (meaning the program with index $i$ isn't total). If the program halts on all inputs in given range from $0$ to $F_B(i)$, then we can actually return 1/true (meaning the program with index $i$ is total). The last sentence is basically true because if the program ever looped on any input it would definitely have looped on input $F(i)-1$ with $F(i) \ge 1$, by definition of $F$. Yet we checked the values till $F_B(i)$, where $F_B(i) > F(i)$.

Now, as to the question of why this means $E_2$ contains an infinite number of elements, I haven't thought it over rigorously, but the numerator in the fraction given in question is a function which isn't $H$-computably bounded while the denominator is a function which is $H$-computably bounded. So by analogy (assuming $f$ to be a function which isn't computably bounded) if I compare with a fraction such as $\frac{f(x)}{x^2}$, it seems 'obvious' to me that definining a set such as $\{\frac{f(1)}{1^2},\frac{f(2)}{2^2},\frac{f(3)}{3^2},\frac{f(4)}{4^2},.....\}$ will contain an infinite number of elements (I have assumed rounding to lower integer after division). This should be made more rigorous though.