An analysis of BMO1

[Pascal Michel]

(1) The following 6x2 Turing machine, called BMO1, was found in April 2004 by "-d"

1RB1RE_1LC0RA_0RD1LB_1RZ1RC_1LF1RF_0LB0LE

Let A(x,y) = 0^inf (01)^(x - 1) 0 1^y E > 0^inf, with x, y > 0

Then we have

(a) 0^inf A > 0^inf --( 10 )--> A(1,2)

(b) if x > y >= 1, A(x,y) --( 6y^2 + 11y + 10 )--> A(x - y, 4y + 2)

(c) if y > x >= 1, A(x,y) --( 4xy + 2x^2 + 3x + 4 )--> A(2x + 1, y - x)

(d) if x = y >=1, A(x,x) --( 6x^2 + 3x + 4 )--> 0^inf (01)^(2x + 2) Z > 0^inf

This machine is conjectured never to halt. See

1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE - BusyBeaverWiki

(2) Let g be the function defined by

g(x,y) = (x - y, 4y + 2)  if x > y

g(x,y) = (2x + 1, y - x)  if y < x

g(x,x) undefined

Let g^k be the kth iterate of g (i.e., g^1 = g and g^(k + 1)(x,y) = g(g^k(x,y)) )

Let us call an ordered pair (x,y) a k-predecessor of a if g^k(x,y) = (a,a).

When you study the future of (x;y) under iterations of g, the following is happening:

 - either an ordered pair (a,a) is quickly reached,

 - or such an ordered pair seems never to be reached.

So it seems that when k grows, the probability that a number a has a k-predecessor becomes very small.

Thus the question is: given an integer k, what is the probability P(k) that a number a has a k-predecessor?

It turns out that this question is not meaningless. The property that a number a has a k-predecessor depends only on the value of a modulo 4^k. So P(k) = N(k)/4^k, where N(k) is the number of integers a in any interval [m + 1, m + 4^k], with m large enough in order to avoid k-predecessors of the form (x,0), (0,y) and (x,x). The condition m = 4^k seems to be sufficient.

(3) Computations give the following values for N(k):

 k          N(k)          N(k) - 2 x  3^(k - 1)

 0              1                  2/3

 1              3                  1

 2              7                  1

 3            19                  1

 4            67                13

 5          175                13

 6          491                  5

 7        1459                  1

 8        4159             -215

 9      12047           -1075

10     36311           -3055

11   107923         -10175

We see that the functionN has a complex behavior.

The following conjecture can be made;

Conjecture 1: for all k >= 1, N(k)  <= 2 x 3^(k - 1) + 13

Conjecture 2: for all k >= 8, N(k)  <= 2 x 3^(k - 1)

This would give, for k >= 8, P(k) <= (2/3) (3/4)^k

It is known that the machine does not halt after 100,000,000 iterations from A(1,2).

But the probability that a number a has a 100,000,000-predecessor is P(100,000,000) < (2/3) (3/4)^100,000,000 < 10^(-10^7)

Maybe this allows one to say that the machine probviously never halts.

[Pascal Michel]

More computations give:

 k          N(k)       N(k) - 2 x 3^(k - 1)

12    322659         -31635

13    959195       -103687

14  2840775       -347871

This is strange, because, if my computations are correct, f(k) = 2 x 3^(k - 1) - N(k) seems to grow faster than a x b^k, with b > 3.

If this behavior goes on, we have the following conjecture:

There exists an integer c such that, for all k > c, N(k) = 0.

This conjecture, with c < 100,000,000, would imply that the machine never halts.

We already know that c > 28, because g^28(22,68) = (2743,2743).

[Shawn Ligocki]

Very interesting, thanks for sharing, Pascal! I haven't thought about backwards reasoning on this function before.

I noticed something interesting while investigating k-predecessors: Even for small k values, some numbers have multiple k-predecessors. For example, we can compute the exact set of values which have k-predecessors:

1-predecessor:

• Every number a != 0 (mod 4) (P(1) = 3/4) has a 1-predecessor (ignoring the edge effects for small values where they run into the (x,0) or (0,x) case)
  
• g(5k+2, k) = (4k+2, 4k+2)
• g(k, 3k+1) = (2k+1, 2k+1)

2-predecessors:

• g^2(21k+12, k) = (16k+10, 16k+10)
  
• g^2(5k+3, 7k+4) = (8k+6, 8k+6)
• g^2(7k+5, 3k+2) = (8k+7, 8k+7)
• g^2(k, 7k+4) = (4k+3, 4k+3)
• At first this seems to be P(2) = 9/16 but this is an overcount b/c all 8k+7 numbers are also 4k+3 numbers!
• So, ex: 7 has two 2-predecessors: (5,2) and (1,11).
• And P(2) = 7/16 as Pascal reported.

But this made me think: I wonder which number is more useful to think about? The fraction of values "a" such that (a,a) = g^k(x,y) (for some (x,y)) or the fraction of values (x,y) such that g^k(x,y) = (a,a) (for some "a")? I think maybe the second one is slightly more meaningful for the probabilistic argument, based on the idea that we are considering all starting points (x,y) as sort of arbitrary and wanting to know how many starting points halt after k steps.

Ex: If there is a lot of "predecessor branching" (in other words, a lot of duplicate inputs that lead to the same output) then it seems plausible that you can have almost all inputs halting, but all to the same small set of values and thus most values would not have k-predecessors for large k.

That said, counting the fraction of (x,y) values which halt in k steps is confusing me a bit and I haven't yet been able to figure out how to quantify it (since the numbers on left are not so well behaved as the ones on right where they only depend on the values mod 4^k).

--
You received this message because you are subscribed to the Google Groups "Busy Beaver Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to busy-beaver-dis...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/busy-beaver-discuss/7a654cc7-3732-4e23-b400-9310dfd551a6n%40googlegroups.com.

[Shawn Ligocki]

If we consider M(k) = the number of k-predecessors of values "a" in the range [m + 1, m + 4^k], then I think this function may be extremely well-behaved. It appears that M(k) = 3^k. I've computed it for k=1,2 in my previous message and have a loose argument for why this should continue.

First, let me talk about the over-under or "GL"-sequence for an iteration of the function g. Basically, it just keeps track of which path was taken in each iteration of g. So if x>y, then the term in the sequence for (x,y) is "G" (greater than) and if x<y, then the first term is "L" (less than). You repeat this on each iteration.

Let's look back at the 2-predecessors:

• GG: g^2(21k+12, k) = (16k+10, 16k+10)
  
• LG: g^2(5k+3, 7k+4) = (8k+6, 8k+6)
• GL: g^2(7k+5, 3k+2) = (8k+7, 8k+7)
• LL: g^2(k, 7k+4) = (4k+3, 4k+3)

I've now annotated each with the GL-sequence that it follows before reaching a halting config (x=y). In other words, every (x,y) that halts in two steps with the sequence "GG" is of the form (21k+12, k) and reaches (16k+10, 16k+10).

Now notice that the coefficient in front of the "k" on the right side of each of these seems to just depend on the number of Ls in the sequence. Specifically it seems like that coefficient is equal to 16 / 2^i if there are "i" Ls. If this pattern holds true, then I think M(k) = sum_{i=0}^k choose(k, i) 2^i = 3^k. The idea here is that for each number of Ls "i", there are (k choose i) GL-sequences with "i" Ls and each will be represented 2^i times within the range [m + 1, m + 4^k].

This still doesn't quite let us compute the fraction of (x,y) that halt in k steps, but it feels maybe a little closer?

[Pascal Michel]

My conjecture (there exists a c such that, for all k > c, N(k) = 0) is obviously false, because

for all a, n > 0, g^n(a - 1, 2^(n + 1) a - n - 1) = (a 2^n - 1, a 2^n - 1),

so, for all k, there exists integers with k-predecessors.

[Pascal Michel]

A correction of a mistake: g^n (a - 1, (2^(n + 1) - 1)a - n - 1) = (a 2^n - 1, a 2^n - 1)