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).