A385902 Antihydra, a BB(6) Turing machine (values of b).

0, 2, 4, 6, 5, 7, 9, 11, 10, 12, 11, 13, 12, 11, 10, 12, 14, 16, 15, 14, 16, 15, 17, 16, 18, 17, 19, 21, 20, 19, 21, 20, 19, 21, 23, 25, 24, 23, 22, 21, 20, 22, 21, 20, 19, 18, 17, 19, 21, 23, 25, 27, 29, 31, 30, 29, 31, 30, 32, 31, 33, 32, 31, 33, 35, 37, 36

Offset: 0

Author

Peter Luschny, Aug 02 2025

Keywords

• nonn

Comments

Let f(a, b) = (3*a / 2, b + 2) if a is even, otherwise ((3*a - 1)/2, b - 1). The Busy Beaver challenge is to find natural numbers n and v, such that after n iterations, starting with f(8, 0), the result is (v, -1). The sequence lists the values of b in the iteration, the values of a are in A386792.

It is strongly suspected that the iteration does not halt according to the random-walk heuristic. Since Antihydra is derived from the transition rules of a 6-state, 2-symbol Turing machine, proving its divergence is equivalent to proving that this machine does not halt. Demonstrating the divergence of Antihydra is likely a necessary step in establishing a lower bound for BB(6), as this Turing machine appears to outrun all known halting 6-state machines.

Links

• Paolo Xausa, Table of n, a(n) for n = 0..10000
• The Busy Beaver Challenge, Antihydra.
• The Busy Beaver Wiki, Antihydra.
• Shawn Ligocki, BB(6) is Hard (Antihydra), Jul 6, 2024.
• Index entries for sequences related to Busy Beaver problem.

Crossrefs

Cf. A386792 (values of a), A028444, A060843.

Programs

Mathematica

Module[{a = 8, b = 0}, NestWhileList[(If[OddQ[a], b--, b += 2]; a += Quotient[a, 2]; b) &, b, b != -1 &, 1, 100]] (* Paolo Xausa, Aug 04 2025 *)

Python

def antihydra(start: int = 8, halt: int = 66) -> list[int]:
    seq = []
    a = start
    b = 0
    n = 0
    while b != -1:
        if n > halt: break
        seq.append(b) # print(f"[{n}] -> ({a}, {b})")
        if a % 2 == 0:
            b += 2
        else:
            b -= 1
        a += a // 2
        n += 1
    return seq
print(antihydra())