cp's OEIS Frontend

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

%I A385902 #26 Aug 05 2025 06:14:42
%S A385902 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,
%T A385902 17,19,21,20,19,21,20,19,21,23,25,24,23,22,21,20,22,21,20,19,18,17,19,
%U A385902 21,23,25,27,29,31,30,29,31,30,32,31,33,32,31,33,35,37,36
%N A385902 Antihydra, a BB(6) Turing machine (values of b).
%C A385902 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.
%C A385902 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.
%H A385902 Paolo Xausa, <a href="/A385902/b385902.txt">Table of n, a(n) for n = 0..10000</a>
%H A385902 The Busy Beaver Challenge, <a href="https://wiki.bbchallenge.org/wiki/Antihydra">Antihydra</a>.
%H A385902 The Busy Beaver Wiki, <a href="https://bbchallenge.org/antihydra">Antihydra</a>.
%H A385902 Shawn Ligocki, <a href="https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html">BB(6) is Hard (Antihydra)</a>, Jul 6, 2024.
%H A385902 <a href="/index/Br#beaver">Index entries for sequences related to Busy Beaver problem</a>.
%t A385902 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 *)
%o A385902 (Python)
%o A385902 def antihydra(start: int = 8, halt: int = 66) -> list[int]:
%o A385902     seq = []
%o A385902     a = start
%o A385902     b = 0
%o A385902     n = 0
%o A385902     while b != -1:
%o A385902         if n > halt: break
%o A385902         seq.append(b) # print(f"[{n}] -> ({a}, {b})")
%o A385902         if a % 2 == 0:
%o A385902             b += 2
%o A385902         else:
%o A385902             b -= 1
%o A385902         a += a // 2
%o A385902         n += 1
%o A385902     return seq
%o A385902 print(antihydra())
%Y A385902 Cf. A386792 (values of a), A028444, A060843.
%K A385902 nonn
%O A385902 0,2
%A A385902 _Peter Luschny_, Aug 02 2025