BusyBeaverWiki - User contributions [en]

User:RobinCodes/Machines at the Edge

2025-12-20T21:41:18Z

Pomme de terre: /* Unknown machines - 9 total */ Fixed typo

= Machines at the Edge =
Some machines are ''right at the edge of computability.'' This means that they are computationally tractable to simulate, but they are literal energy vampires. There are a few such machines that have been found, and all of them should be listed here. Some of them, however, are not yet confirmed to be tractable or intractable.

There are no energy vampire machines in [[BB(3,3)]], one unknown in [[BB(2,5)]] and for [[BB(6)]], two machines, seven intractable machines and 9 others, which have not yet been worked out.

== [[BB(6)|6x2]] Machines ==

=== {{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}} (CRYPTID) ===

* Would take a '''few weeks''' with '''~10 TB of memory.'''
* '''50% chance of halting''' based on H^114e12(10) mod 4.
* Mechanism: approximately B(m) ~ B(H^m(10)).
* ~$200 of compute.

=== {{TM|1RB0LA_0RC0RB_1LD1LA_1LC1RE_1RF0RD_1LC---}} ===

* Around '''a day''' with somewhere '''in [100, 1000] GB of memory.'''
* Expected to halt on the order of one trillion iterations.
* Mechanism: pipe [[Hydra]] residues into another very chaotic machine.

=== Unknown machines - 9 total ===
The following 6 machines are all possibly tetrational machines, given by Racheline [https://discord.com/channels/960643023006490684/1026577255754903572/1384906806303789178 here]. It is not yet known whether they are intractable.<syntaxhighlight lang="html">1RB1LE_0LC1RE_---1LD_0RD1LA_0RF1RF_1RA0LB
1RB1RD_1LC1RA_---1LD_1LE0RA_1LF0LE_0RB0LB
1RB0RC_0RC0RA_1RD1LA_1LE0LB_0LB1LF_0LD---
1RB0LF_0RC1RB_1LD0RB_1LE---_1RF1LA_0LC0LE
1RB0LE_0RC0RA_1LD0LC_1LA0LB_1RA1LF_---0LC
1RB1RF_1LC0RA_---0LD_0LE0LB_1RF1RB_1RE1LF - Probviously halts after 10^10^O(1) steps - Racheline</syntaxhighlight>The following 3 machines are all probviously halting [[Cryptid|cryptids]].<syntaxhighlight lang="html">1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA
1RB1LD_1RC0LE_1LA1RE_0LF1LA_1RB0RB_---0LB
1RB0RE_1LC0RA_1LA1LD_1LC1LF_0LC0LB_1LE--- - Equivalent to the first in this list (?)</syntaxhighlight>

== Intractable 6x2 machines ==
7 more machines, all which are probviously halting [[Cryptid|cryptids]].

=== {{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}} CRYPTID ===

* Uses the [[Hydra function|Hydra map]]
* The lower bound for when it halts is around 10^10^120395, and with each exponentiation it has a 1/4 chance of halting, so I think the expected halting time is around 10^10^10^10^10^120395 - Racheline

=== {{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}} CRYPTID ===

* Next reset in ~10^22.17 iterations of the [[Hydra function|Hydra map]], by [https://discord.com/channels/960643023006490684/1448725136340422717/1450045543710724107 residual-integral]
* It would cost at least $40B and take three million years to simulate

=== {{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}} CRYPTID ===

* Next reset in ~10^1481 iterations of a near-[[Hydra function|Hydra map]], by [https://discord.com/channels/960643023006490684/1448725136340422717/1450045543710724107 residual-integral]

=== {{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}} CRYPTID ===

* Next reset in ~10^446 iterations of [[Hydra function|Hydra map]], by [https://discord.com/channels/960643023006490684/1448725136340422717/1450045543710724107 residual-integral]

=== {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC}} CRYPTID ===

* Next reset in ~10^24684623 iterations of near-[[Hydra function|Hydra map]], by [https://discord.com/channels/960643023006490684/1448725136340422717/1450045543710724107 residual-integral]
* Canonical machine of a class of 16 probable halters.

=== {{TM|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}} CRYPTID ===

* One of the values for the current rules is so large now, that using these rules, simulating is no longer a viable option to show halting. ~10^39991 to next reset.

=== {{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}} Lucy's Moonlight | CRYPTID ===

* Next reset in ~10^2901 iterations of near-[[Hydra function|Hydra map]], by [https://discord.com/channels/960643023006490684/1448725136340422717/1450045543710724107 residual-integral]

== [[BB(2,5)|2x5]] Machines ==

=== {{TM|1RB2RA3LB---2LB_2LA0LA4RB0RB1LA}} ===

* Racheline estimates that it has a 1/8 chance of beating the current champion.
* Wheter it is tractable to simulate until halting or not is not yet known.

Skelet 1

2025-10-30T03:30:29Z

Pomme de terre: /* See Also */ Fixed incorrect date

{{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC}}{{unsolved|What is the exact cycle preperiod of Skelet 1?}}{{Stub}}
[[File:Skeleton warrior.png|thumb|A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.]]
{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}, called '''Skelet #1''', was one of [[Skelet's 43 holdouts]] and one of the last holdouts in [[BB(5)]]. It was eventually proven to be a [[Translated Cycler]] by Pavel Kropitz and Shawn Ligocki.

It has a period 8,468,569,863 and start step about <math>5.42 \times 10^{51}</math>.<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#stats Skelet #1 is infinite] Statistics.</ref> Both of these values are gigantic in comparison to the runtime of the [[5-state busy beaver winner]] which runs for a "mere" 47 million steps.

== Preperiod ==
The exact preperiod (minimum cycle start start step) for Skelet 1 is not known, but @hipparcos computed it to be approximately 5418883027667422764169643414989497193809945789706483. This is an upper bound (by this point the TM is cycling). This value is probably accurate to within about one period.<ref>[https://discord.com/channels/960643023006490684/1075378436404678707/1328263736686936066 @hipparcos 13 Jan 2025 Discord]</ref>

== References ==
<references />

== See Also ==
* [https://www.sligocki.com/2023/02/25/skelet-1-wip.html Skelet #1: What I Know]. 25 Feb 2023. Shawn Ligocki
* [https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html Skelet #1: A Halting Counter Config]. 27 Feb 2023. Shawn Ligocki
* [https://www.sligocki.com/2023/03/13/skelet-1-infinite.html Skelet #1 is infinite ... we think]. 13 Mar 2023. Shawn Ligocki
* Simulation code by Pavel & Shawn: https://github.com/univerz/bbc/tree/no1
[[Category:BB(5)]]

Beaver Math Olympiad

2025-10-26T21:54:16Z

Pomme de terre: BMO7 solved

'''Beaver Mathematical Olympiad''' (BMO) is an attempt to re-formulate the halting problem for some particular Turing machines as a mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of the BMO is twofold. First, statements where non-essential details (related to tape encoding, number of steps, etc.) are discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

== Unsolved problems ==

=== 1. {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (1, 2)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n-b_n, 4b_n+2) & \text{if }a_n \ge b_n \\
(2a_n+1, b_n-a_n) & \text{if }a_n < b_n
\end{cases}</math>

for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_i = b_i</math>?

The first 10 values of <math>(a_n, b_n)</math> are <math>(1, 2), (3, 1), (2, 6), (5, 4), (1, 18), (3, 17), (7, 14), (15, 7), (8, 30), (17, 22)</math>.

=== 2. [[Hydra]] and [[Antihydra]] ===

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_{n+1} = a_n+\left\lfloor\frac{a_n}{2}\right\rfloor</math> for all non-negative integers <math>n</math>.

# If <math>a_0=3</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many even numbers as odd numbers? ([[Hydra]])
# If <math>a_0=8</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many odd numbers as even numbers? ([[Antihydra]])

=== 5. {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (0, 5)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n+1, b_n-f(a_n)) & \text{if } b_n \ge f(a_n) \\
(a_n, 3b_n+a_n+5) & \text{if } b_n < f(a_n)
\end{cases}</math>

where <math>f(x)=10\cdot 2^x-1</math> for all non-negative integers <math>x</math>.

Does there exist a positive integer <math>i</math> such that <math>b_i = f(a_i)-1</math>?

=== 6. {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}} ===
Let <math>f(b) = b + k + 3a</math>, where <math>k</math> and <math>a</math> are non-negative integers satisfying <math>b = (2a+1)\cdot 2^k</math>.

Now consider the iterated application of the function <math>f^{n+1}(b) = f(f^n(b)))</math>, <math>f^0(b)=b</math>. Does there exist a non-negative integer <math>n</math> such that <math>f^n(6)</math> equals a power of 2?

== Solved problems ==

=== 3. {{TM|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} and {{TM|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} ===

Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>. Let <math>(a_n)_{n \ge 0}</math> be a sequence such that

<math display="block">a_n = \begin{cases}
2 & \text{if } n=0 \\
a_{n-1}+2^{v_2(a_{n-1})+2}-1 & \text{if } n \ge 1
\end{cases}</math>

for all non-negative integers <math>n</math>. Is there an integer <math>n</math> such that <math>a_n=4^k</math> for some positive integer <math>k</math>?

Link to Discord discussion: https://discord.com/channels/960643023006490684/1084047886494470185/1252634913220591728

=== 4. {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB|non-halt}} ===

Bonnie the beaver was bored, so she tried to construct a sequence of integers <math>\{a_n\}_{n \ge 0}</math>. She first defined <math>a_0=2</math>, then defined <math>a_{n+1}</math> depending on <math>a_n</math> and <math>n</math> using the following rules:

* If <math>a_n \equiv 0\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n}{3}+2^n+1</math>.
* If <math>a_n \equiv 2\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n-2}{3}+2^n-1</math>.

With these two rules alone, Bonnie calculates the first few terms in the sequence: <math>2, 0, 3, 6, 11, 18, 39, 78, 155, 306, \dots</math>. At this point, Bonnie plans to continue writing terms until a term becomes <math>1\text{ (mod 3)}</math>. If Bonnie sticks to her plan, will she ever finish?

<div class="toccolours mw-collapsible mw-collapsed">'''Solution'''<div class="mw-collapsible-content">
How to guess the closed-form solution: Firstly, notice that <math>a_n \approx \frac{3}{5} \times 2^n</math>. Secondly, calculate the error term <math>a_n - \frac{3}{5} \times 2^n</math>. The error term appears to have a period of 4. This leads to the following guess:

<math display="block">a_n=\frac{3}{5}\begin{cases}
2^n+\frac{7}{3} &\text{if } n\equiv 0 \pmod{4}\\
2^n-2 &\text{if } n\equiv 1 \pmod{4}\\
2^n+1 &\text{if } n\equiv 2 \pmod{4}\\
2^n+2 &\text{if } n\equiv 3 \pmod{4}
\end{cases}</math>

This closed-form solution can be proven correct by induction. Unfortunately, the induction may require a lot of tedious calculations.

For all <math>k</math>, we have <math>a_{4k} \equiv 2\text{ (mod 3)}</math> and <math>a_{4k+1} \equiv a_{4k+2} \equiv a_{4k+3} \equiv 0\text{ (mod 3)}</math>. Therefore, Bonnie will never finish.
</div></div>

=== 7. {{TM|1RB1RF_1RC0RA_1LD1RC_1LE0LE_0RA0LD_0RB---|non-halt}} ===
Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>.

Let <math>f(n) = n+1+(v_2(n+1) \bmod 2)</math>.

Now consider the iterated application of the function <math>f^{n+1}(b) = f(f^n(b)))</math>, <math>f^0(b)=b</math>.

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_0=1</math> and <math>a_{n+1} = f^{n+2}\left(\left\lfloor\frac{a_n}{2}\right\rfloor\right)</math> for all non-negative integers <math>n</math>.

Does there exist a non-negative integer <math>k</math> such that <math>a_k</math> is even?

(for simplicity, this question is slightly stronger than the halting problem of this TM)

Link to Discord discussion: https://discord.com/channels/960643023006490684/1421782442213376000/1431483206208852001

== Practice Problems ==
Problems that are not BMO-level, but provide counter-examples to certain [[probvious]] intuition:

* {{TM|1RB0LE_1LC1RA_---1LD_0RB1LF_1RD1LA_0LA0RD}}
* {{TM|1RB0RD_0LC1RA_0RA1LB_1RE1LB_1LF1LB_---1LE}}

Antihydra

2024-07-02T14:48:54Z

Pomme de terre: link to numbers

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 <nowiki>A(a+4, b) = ^ 1^b 0 1^a E> $</nowiki>

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].
[[Category:Individual machines]]