3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can I assume that $\text{Pr}(P_1 = 1) = 0$ and $\text{Pr}(P_2 = 1) = 1$, but it is not possible to estimate $\text{Pr}(P_2 = 1, P_3 = 1)$ or $\text{Pr}(P_2 = 1, P_3 = 1, P_4 = 1)$, where $\text{Pr}$ denotes the probability, $P_X = 1$ denotes "Possibility $X$ is true" and $\text{Pr}(S) = 1$ denotes "the probability of statement $S$ being true is equal to 100%"? $\endgroup$ Apr 6, 2018 at 7:39
  • $\begingroup$ $e^{i \pi}$. Collaborative mathematics should not involve unnecessarily circumlocutory and confusing use of notations which disguise meaning rather than elucidate it. $\endgroup$ Apr 6, 2018 at 20:37
  • $\begingroup$ In other words, can I assume that there does not exist a finite integer $a$ such that $a$ is greater than any element of the sequence $E_2$? $\endgroup$ Apr 7, 2018 at 12:11
  • $\begingroup$ Correct, yes, and therefore $E_2$ takes on infinitely many distinct values. $\endgroup$ Apr 7, 2018 at 15:24
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Does "an infinite number of elements" in this answer imply an infinite number of different integers (so that Possibility 1 is false )? $\endgroup$ Apr 7, 2018 at 8:35
  • $\begingroup$ I think I have some sense of what you are trying to say w.r.t. to possibility(4). But, strictly speaking, a set doesn't contain repetitions. So, from that perspective, you can write down three mutually exclusive possibilities: (1) $E_2$ contains finitely many elements (2) $E_2$ contains an infinite number of elements but is not equal to $\mathbb{N}$ (3) $E_2$ is equal to $\mathbb{N}$. So yes, from that perspective it seems that possibility(1) doesn't occur and one of possibilities(2) and (3) should be correct. Regarding what you wrote as possibility(4), it isn't fully clear to me (cont.) $\endgroup$
    – SSequence
    Apr 7, 2018 at 10:12
  • $\begingroup$ what that means "exactly". But I assume you are talking about repetition or non-repetition of terms (after evaluation) that occur in definition of $E_2$ (in your question). So it would probably count as a further restriction of possibilities (2) and (3) in my comment just above. Also, I think that possibility(1) is also ruled out by the other answer given (but I couldn't fully understand the construction). $\endgroup$
    – SSequence
    Apr 7, 2018 at 10:15
  • $\begingroup$ I should have used the term “sequence” instead of a “set”: for example, the infinite sequence $\{0, 1, 1, 2, 2, 2, 3, \ldots\}$ contains all integers, but the infinite sequence $\{0, 0, 1, 0, 1, 2, 0, 1, 2, 3, \ldots\}$ contains infinitely many occurrences of any integer. They both evaluate to the same set, but the original sequences are significantly different. $\endgroup$ Apr 7, 2018 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.