1RB2LA1LA_2LA0RA2RC_---0LC2RA

From BusyBeaverWiki
Revision as of 17:12, 14 January 2025 by Sligocki (talk | contribs)
Jump to navigation Jump to search

1RB2LA1LA_2LA0RA2RC_---0LC2RA (bbch)

Also known as "Wily Coyote." This is BB(3,3) holdout #531. It is equivalent to BB(3,3) holdout #532 1RB2LA1LA_2LA0RA2RC_---1RB2RA (bbch), as found by @dyuan01.

@Legion wrote a simulator in Rust for this TM that can be found here. They described the behavior of this machine as

"The left side is just bouncing around a 1212... pattern, nothing interesting there. But the right side has this extremely peculiar 'binary counter'. Since the head never moves more than a fixed number of cells (3, but effectively only 1) from right to left before finally resetting, we know that all information must flow from left to right. Therefore, it acts somewhat like a binary counter, in the sense that each cell must follow an eventually-periodic pattern as long as the machine doesn't halt, and that period is a non-decreasing power of 2. But as we look further to the right, the pattern actually gets more and more complex, as opposed to the trivial back-and-forth flipping of a real binary counter. The attached program calculates the pattern for each cell, as a function of the previous cell's pattern; by cell 99, the pattern is 11531 lines long. My current hope is in how repetitive the pattern appears; it often has just BBBB..., CCCC..., or ADAD... for hundreds of lines straight. So it might be bounded in how much information it actually contains, which would open a pathway for proving it non-halting."

@Racheline wrote an accelerated simulator of this TM in Python:

def f():
    global x, r, newr
    for s in r[-1]:
        i = 0
        while s != 3:
            if i >= len(x):
                if s == 1:
                    print("halted")
                    exit()
                elif s == 2:
                    x += [1, 1, 0, 0]
                else:
                    x.append(0)
                break
            x[i], s = x[i] ^ (s >> 1) ^ 1, [1, 3, 2, 2, 0, 1][3 * x[i] + s]
            i += 1
            if i == 1:
                newr.append(s)
        if s == 3:
            if i < len(x):
                x[i] ^= 1
            else:
                x += [0, 0]


x = [0, 0]
y = [0, 0]
p = [1]
r = [[0, 1]]
for n in range(160):
    newr = []
    f()
    if x[0] != y[0]:
        f()
        p.append(p[-1] + 1)
    else:
        p.append(p[-1])
    r.append(newr)
    if len(y) == 1:
        newr = []
        x = []
        f()
        y = [i for i in x]
    else:
        y.pop(0)
        x = [i for i in y]
print(p[1:])


This is Legion's "pet machine."