Antihydra

Unsolved problem:

Does Antihydra run forever?

Artistic depiction of Antihydra by Jadeix

Antihydra is the 6-state 2-symbol machine 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch).

This machine was the first identified BB(6) Collatz-like Cryptid, and is closely related to Hydra.

It simulates the Collatz-like iteration

$${\begin{array}{l}A(2a,&b)&\to &A(3a,&b+2)\\A(2a+1,&b)&\to &A(3a+1,&b-1)&{\text{if}}&b>0\\A(2a+1,&0)&\to &{\text{HALT}}\end{array}}$$

starting from $A(8,0)$, using configurations of the form $A(a+4,b)=0^{\infty }\;1^{b}\;0\;1^{a}\;E>\;0^{\infty }$.

It was discovered by mxdys on 28 Jun 2024 and shared on Discord.

Racheline found that compared to the Hydra iteration, this one starts at (8, 0) rather than (3, 0), and the roles of odd and even a are exchanged (in terms of which increases b by two, and which decrements b or halts). Obstacles to proving the long-run behavior are equally serious. Like the Hydra iteration, this one is biased toward increasing the value of b (assuming equal chances of adding +2 or -1).

There is no halt in the first 11.8 million iterations, by which point b has reached 5890334 (which means that it also does not halt in the first 17690334 iterations).

Simulator

Two simulators are available. A fast simulator written in Rust for the odd/even sequence used by Antihydra is available here.

Alternatively, here is a GMP implementation of the program with some performance diagnostics added:

/* Tested on GMP 6.3.0, Ubuntu 24.04. */

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>

#include <gmp.h>

static uint64_t get_milis(void) {
    struct timespec ts;
    timespec_get(&ts, TIME_UTC);
    return (uint64_t)(ts.tv_sec * 1000 + ts.tv_nsec/1000000);
}

int main(int argc, char **argv) {
    char *as, *bs;
    mpz_t a, aq, ar, b;
    uint64_t i, time, newtime;

    /* CLI and init. */
    if (argc > 1) {
        as = argv[1];
    } else {
        as = "8";
    }
    if (argc > 2) {
        bs = argv[2];
    } else {
        bs = "0";
    }
    mpz_init_set_str(a, as, 10);
    mpz_init_set_str(b, bs, 10);
    mpz_init(aq);
    mpz_init(ar);
    i = 0;
    time = get_milis();

    /* Run. */
    while (1) {
        /* aq = a / 2
         * ar = a % 2 */
        mpz_fdiv_qr_ui(aq, ar, a, 2);
        if (
            /* odd */
            mpz_cmp_ui(ar, 0)
        ) {
            if (!mpz_cmp_ui(b, 0)) break;
            /* a = aq * 3 + 1 */
            mpz_mul_ui(a, aq, 3);
            mpz_add_ui(a, a, 1);
            /* b -= 1 */
            mpz_sub_ui(b, b, 1);
        } else {
            /* a = aq * 3 */
            mpz_mul_ui(a, aq, 3);
            /* b += 2 */
            mpz_add_ui(b, b, 2);
        }
        i++;
        if (i % 100000 == 0) {
            newtime = get_milis();
            gmp_printf("%" PRIu64 " ms=%" PRIu64 " log10(a)=%ju log10(b)=%ju\n",
                       i/100000, newtime - time, mpz_sizeinbase(a, 10), mpz_sizeinbase(b, 10));
            time = newtime;
        }
    }

    /* Cleanup if we ever reach it. */
    mpz_clear(a);
    mpz_clear(aq);
    mpz_clear(ar);
    mpz_clear(b);
    return 0;
}‎

Compile and run with:

gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out‎

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.