Antihydra

2024-07-11T08:55:06Z

Cirosantilli: fix code oops

Antihydra is the 6-state 2-symbol machine [https://bbchallenge.org/1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA https://bbchallenge.org/1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA].

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

It simulates the Collatz-like iteration

<math display="block">\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}</math>
<br>
starting from A(8, 0),
<br>
using configurations of the form <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>

It was discovered by mxdys on 28 Jun 2024 and shared on Discord [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318].

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) [https://discord.com/channels/960643023006490684/1026577255754903572/1256403772998029372].

Here is a GMP implementation of the program with some performance diagnostics added:

‎<syntaxhighlight lang="c">
/* 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;
}
‎</syntaxhighlight>

Compile and run with:

‎<syntaxhighlight lang="bash">
gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out
‎</syntaxhighlight>

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.
[[Category:Individual machines]]

Antihydra

2024-07-10T10:14:16Z

Cirosantilli: Add GMP implementation of the problem.

Antihydra is the 6-state 2-symbol machine [https://bbchallenge.org/1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA https://bbchallenge.org/1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA].

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

It simulates the Collatz-like iteration

<math display="block">\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}</math>
<br>
starting from A(8, 0),
<br>
using configurations of the form <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>

It was discovered by mxdys on 28 Jun 2024 and shared on Discord [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318].

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) [https://discord.com/channels/960643023006490684/1026577255754903572/1256403772998029372].

Here is a GMP implementation of the program with some performance diagnostics added:

‎<syntaxhighlight lang="c">
#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;

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();
while (1) {
mpz_fdiv_qr_ui(aq, ar, a, 2);
if (!mpz_cmp_ui(ar, 0)) {
mpz_mul_ui(a, aq, 3);
mpz_add_ui(b, b, 2);
} else {
if (!mpz_cmp_ui(ar, 0)) break;
mpz_mul_ui(a, aq, 3);
mpz_add_ui(a, a, 1);
mpz_sub_ui(b, b, 1);
}
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;
}
}

mpz_clear(a);
mpz_clear(aq);
mpz_clear(ar);
mpz_clear(b);
return 0;
}
‎</syntaxhighlight>

Compile and run with:

‎<syntaxhighlight lang="bash">
gcc -ggdb3 -O2 -pedantic-errors -std=c11 -Wall -Wextra -o 'antihydra.out' 'antihydra.c' -lgmp
./antihydra.out
‎</syntaxhighlight>

Tested on Tested on GMP 6.3.0, Ubuntu 24.04.
[[Category:Individual machines]]

BusyBeaverWiki - User contributions [en]

Antihydra

Antihydra