Antihydra

From BusyBeaverWiki
Jump to navigation Jump to search
Unsolved problem:
Does Antihydra run forever?

1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch), called Antihydra, is a BB(6) Cryptid. Its pseudo-random behaviour was first reported on Discord by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after. It was named after the 2-state, 5-symbol Turing machine called Hydra for sharing many similarities to it.[1]

Antihydra is known to not generate Sturmian words[2] (Corollary 4).


Artistic depiction of Antihydra by Jadeix
      
0 1
A 1RB 1RA
B 0LC 1LE
C 1LD 1LC
D 1LA 0LB
E 1LF 1RE
F --- 0RA

The transition table of Antihydra.

      

State diagram of Antihydra

      
A community trophy - to be awarded to the first person or group who solves the Antihydra problem

Analysis

Let A(a,b):=01a01bE>0. Then,[3] A(a,2b)2a+3b2+12b+11A(a+2,3b+2),A(0,2b+1)3b2+9b10<F11013b0,A(a+1,2b+1)3b2+12b+5A(a,3b+3).

Proof

Consider the partial configuration P(m,n):=01mE>01n0. The configuration after two steps is 01m10A>1n+10. We note the following shift rule: A>1ss1sA> As a result, we get 01m101n+1A>0 after n+1 steps. Advancing two steps produces 01m101n+2<C0. A second shift rule is useful here: 1s<Cs<C1s This allows us to reach 01m10<C1n+20 in n+2 steps. Moving five more steps gets us to 01m2E>01n+30, which is the same configuration as P(m2,n+3). Accounting for the head movement creates the condition that m4. In summary: P(m,n)2n+12P(m2,n+3) if m4. With A(a,b) we have P(b,0). As a result, we can apply this rule 12b1 times (assuming b4), which creates two possible scenarios:

  1. If b0 (mod2), then in i=0(b/2)2(2×3i+12)=34b2+32b6 steps we arrive at P(2,32b3). The matching complete configuration is 01a011E>01(3b)/230. After 3b+4 steps this is 01a<C001(3b)/20, which then leads to 0<C1a001(3b)/20 in a steps. After five more steps, we reach 01E>1a+2001(3b)/20, from which another shift rule must be applied:E>1ss1sE>Doing so allows us to get the configuration 01a+3E>001(3b)/20 in a+2 steps. In six steps we have 01a+2011E>1(3b)/20, so we use the shift rule again, ending at 01a+201(3b)/2+2E>0, equal to A(a+2,32b+2), 32b steps later. This gives a total of 2a+34b2+6b+11 steps.
  2. If b1 (mod2), then in 34b2274 steps we arrive at P(3,3b92). The matching complete configuration is 01a0111E>01(3b9)/20. After 3b+2 steps this becomes 01a<F1101(3b3)/20. If a=0 then we have reached the undefined F0 transition with a total of 34b2+3b194 steps. Otherwise, continuing for six steps gives us 01a10111E>1(3b3)/20. We conclude with the configuration 01a101(3b+3)/2E>0, equal to A(a1,3b+32), in 3b32 steps. This gives a total of 34b2+92b14 steps.

The information above can be summarized as A(a,b){A(a+2,32b+2)if b2,b0(mod2);0<F1101(3b3)/20if b3,b1(mod2), and a=0;A(a1,3b+32)if b3,b1(mod2), and a>0. Substituting b2b for the first case and b2b+1 for the other two yields the final result.

In effect, the halting problem for Antihydra is about whether repeatedly applying the function f(n)=3n2+2 will at some point produce more odd values of n than twice the number of even values.

These rules can be modified to use the function H(n)=3n2, or the Hydra function, which strengthens Antihydra's similarities to Hydra.

Trajectory

Path of parity of repeated applications of Hydra map for Antihydra.

Starting from a blank tape, Antihydra reaches A(0,4) in 11 steps and then the rules are repeatedly applied. So far, Antihydra has been simulated to 238 rule steps,[4] at which point a exceeds 237. Here are the first few: A(0,4)47A(2,8)111A(4,14)250A(6,23)500A(5,36)1209A(7,56)2713A(9,86) The trajectory of a values resembles a random walk in which the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. If P(n) is the probability that the walker will reach position -1 from position n, then it can be seen that P(n)=12P(n1)+12P(n+2). Solutions to this recurrence relation come in the form P(n)=c0(512)n+c1+c2(1+52)n, which after applying the appropriate boundary conditions reduces to P(n)=(512)n+1. This means that if the walker were to get to the position of the current a value, then the probability of it ever reaching position -1 is less than (512)2372.884×1028723042565. This combined with the fact that the expected position of the walker after k steps is 12k strongly suggests Antihydra probviously runs indefinitely.

Code

The following Python program implements the abstracted behavior of the Antihydra. Proving whether it halts or not would also solve the Antihydra problem:

# Current value of the iterated Hydra function starting with initial value 8 (the values do not overflow)
h = 8
# (Collatz-like) condition counter that keeps track of how many odd and even numbers have been encountered
c = 0
# If c equals -1 there have been (strictly) more than twice as many odd as even numbers and the program halts
while c != -1:
    # If h is even, add 2 to c so even numbers count twice
    if h % 2 == 0:
        c += 2
    else:
        c -= 1
    # Add the current hydra value divided by two (integer division, rounding down) to itself (Hydra function)
    # Note that integer division by 2 is equivalent to one bit shift to the right (h >> 1)
    h += h//2

The variable values of this iteration have been put into the On-Line Encyclopedia of Integer Sequences (OEIS):

Fast Hydra/Antihydra simulation code by Greg Kuperberg (who said it could be made faster using FLINT):

# Python script to demonstrate almost linear time hydra simulation
# using fast multiplication. 
# by Greg Kuperberg

import time
from gmpy2 import mpz,bit_mask

# Straight computation of t steps of hydra
def simple(n,t):
    for s in range(t): n += n>>1
    return n

# Accelerated computation of 2**e steps of hydra
def hydra(n,e):
    if e < 9: return simple(n,1<<e)
    t = 1<<(e-1)
    (p3t,m) = (mpz(3)**t,bit_mask(t))
    n = p3t*(n>>t) + hydra(n&m,e-1)
    return p3t*(n>>t) + hydra(n&m,e-1)

def elapsed():
    (last,elapsed.mark) = (elapsed.mark,time.process_time())
    return elapsed.mark-last
elapsed.mark = 0

(n,e) = (mpz(3),25)

elapsed()
print('hydra:  steps=%d hash=%016x time=%.6fs'
    % (1<<e,hash(hydra(n,e)),elapsed()))

# Quadratic time algorithm for comparison
# print('simple: steps=%d hash=%016x time=%.6fs'
#     % (1<<e,hash(simple(n,1<<e)),elapsed()))

References

  1. Discord conversation where the machine was named
  2. DUBICKAS A. ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS. Glasgow Mathematical Journal. 2009;51(2):243-252. doi:10.1017/S0017089508004655
  3. S. Ligocki, "BB(6) is Hard (Antihydra)" (2024). Accessed 22 July 2024.
  4. https://discord.com/channels/960643023006490684/1026577255754903572/1271528180246773883