BusyBeaverWiki - User contributions [en]

File:BB6 holdouts 4741-1.txt

2024-09-24T05:07:15Z

DF376:

Holdouts lists

2024-09-02T18:03:22Z

DF376:

A '''holdout''' (or undecided machine) is a [[Turing machine]] for which it is not known whether the machine halts or not from all-0 input tape. Holdouts are the machines which [[Decider|deciders]] are unable to decide.

Holdout lists are often shared by contributors:

{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098 September 2, 2024]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13th 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9th 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7th 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22nd 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(5)]]
|
|
|0
|
|
|}
Georgi Georgiev (Skelet) posted [https://skelet.ludost.net/bb/nreg.html a list of 43 holdouts] for BB(5) in 2003. bbchallenge.org successfully reduced the number of holdouts for BB(5) to zero in June 2024.

Holdouts lists

2024-09-02T18:02:52Z

DF376:

A '''holdout''' (or undecided machine) is a [[Turing machine]] for which it is not known whether the machine halts or not from all-0 input tape. Holdouts are the machines which [[Decider|deciders]] are unable to decide.

Holdout lists are often shared by contributors:

{| class="wikitable sortable"
|+
!BB space
!Date
!Shared by
!Number of holdouts
!File
!Notes
|-
|[[BB(6)]]
|[https://discordapp.com/channels/960643023006490684/1239205785913790465/1280185195877634098]
|@mxdys
|5394
|[[:File:BB6 holdouts 5394.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1269612923127599164 August 4, 2024]
|@mxdys
|5877
|[[:File:BB6 holdouts 5877.txt]]
|
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1259131753176498216 July 6, 2024]
|@mxdys
|7296
|[[:File:BB6 holdouts 7296.txt]]
|
|-
|[[BB(2,5)]]
|June 15th 2024
|@dyuan01
| 273
|[[:File:2x5_holdouts_273.txt]]
|@Justin Blanchard's 499 holdouts minus machines solved by @mxdys
|-
|[[BB(6)]]
|[https://discord.com/channels/960643023006490684/1239205785913790465/1250895665719148595 June 13th 2024]
|@tjligocki
| 12,091
|[[:File:BB6 holdouts 12091.txt]]
|Work done with @Shawn Ligocki
|-
|[[BB(3,3)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1249142547217907772 June 9th 2024]
|@Justin Blanchard
|22
|[[:File:3x3.todo.txt]], [[:File:Mugshots small.pdf]]
|
|-
|BB(6)
|[https://discord.com/channels/960643023006490684/1239205785913790465/1248708916381220954 June 7th 2024]
|@mxdys
|12,325
|[[:File:BB6 holdouts 12325.txt]]
|Some equivalent machines are removed.
|-
|[[BB(2,5)]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1242679236142170203 May 22nd 2024]
|@Justin Blanchard
|499
|[[:File:2x5.todo.txt]]
|
|-
|[[BB(5)]]
|
|
|0
|
|
|}
Georgi Georgiev (Skelet) posted [https://skelet.ludost.net/bb/nreg.html a list of 43 holdouts] for BB(5) in 2003. bbchallenge.org successfully reduced the number of holdouts for BB(5) to zero in June 2024.

File:BB6 holdouts 5394.txt

2024-09-02T18:01:08Z

DF376:

Champions

2024-08-18T20:37:12Z

DF376: Undo revision 745 by Azerty (talk) They can't be equal since we are using aproximations of the true value of the machines

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|Discovered by Racheline in 2024
|-
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(13)
|
|
|
|-
|BB(14)
|<math> > f_{\omega + 1}(65536) > g_{64} </math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|Discovered by Racheline in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|
|}

== 4-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,4)
|<math>\geq3,932,964</math>
|
|
|-
|BB(3,4)
|<math>>2\uparrow^{15}5</math>
|
|
|}

== 5-Symbol TMs ==
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|BB(2,5)
|<math>>10^{10^{10^{3314360}}}</math>
|
|
|}

== References ==
<references />

Champions

2024-08-15T15:25:27Z

DF376: /* 3-Symbol TMs */ Added the BB(3,3) current champion.

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Discovered by Racheline in 2024
|-
|BB(9)
|
|
|
|-
|BB(10)
|<math> > f_\omega^2(25) </math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Discovered by Racheline in 2024
|-
|BB(11)
|
|
|
|-
|BB(12)
|
|
|
|-
|BB(13)
|<math> > f_\omega^4(70) </math>
|{{TM|1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(14)
|
|
|
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) > g_{64} </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== 3-Symbol TMs ==

{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2,3)]]
|38
|{{TM|1RB2LB---_2LA2RB1LB|halt}}
|
|-
|[[BB(3,3)]]
|<math> > 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|-
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|
|
|}

== References ==
<references />

Champions

2024-08-14T17:45:16Z

DF376: /* 2-Symbol TMs */ Clarification in the notation.

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy].
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|
|
|
|-
|BB(9)
|<math>> 10 \uparrow\uparrow 30</math>
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG|halt}}
|Designed by Milton Green in 1964 ([[Green's machines]])
|-
|BB(10)
|<math> > 10 \uparrow\uparrow 10^{10^{12}} </math>
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH|halt}}
|[[Green's machines]]
|-
|BB(11)
|<math> > 10 \uparrow\uparrow\uparrow 10^{12} </math>
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI|halt}}
|[[Green's machines]]
|-
|BB(12)
|<math> > 2 \uparrow^{12} 4 > f_{13}(2) </math>
|{{TM|1RB1LL_0RC1RC_1LD1LG_0RE1LC_1LD1RF_1RE1RI_1RH0LA_---0RF_0RB1LJ_---0LK_0LF1LF_1RZ0LA|halt}}
|[https://github.com/sligocki/sligocki.github.io/issues/7#issuecomment-2143486164 Compilation] of a BB(3,4) TM by <code>@Iijil1</code> in 2024
|-
|BB(13)
|<math> > f_\omega^4(70) </math>
|{{TM|1RJ1RH_1RC1RB_1LI0RD_1RC1LE_0LE1LF_1LG1RH_1RB0LF_0RA1LE_1RF1LJ_0LK1RZ_1LL1LK_1LM1LM_0LI0LL|halt}}
|Discovered by Racheline in 2024
|-
|BB(14)
|
|
|
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) > g_{64} </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== References ==
<references />

1RB0RF 1RC0LD 1LB1RC ---0LE 1RA1LE ---0RC

2024-08-13T13:59:05Z

DF376:

{{machine|1RB0RF_1RC0LD_1LB1RC_---0LE_1RA1LE_---0RC}}
{{TM|1RB0RF_1RC0LD_1LB1RC_---0LE_1RA1LE_---0RC|undecided}}

A machine on the critical path to proving the busy beaver value "BB(6, 2, 2)" (6-state, 2-symbol, 2 undefined transitions).
(Machines [[1RB0RB_1LC1RB_---0LD_1RA0LE_1RF1LE_---0RA]], [[1RB1LA_1LA0RC_---0RD_1LE1RD_0LA0LF_---0LA]], and [[1RB1LA_1LA0RC_---0RD_1LE1RD_1LB0LF_---0LA]] <ref>The [[Holdouts lists|holdout list]] omits the last one. Since holdout lists are useless, it's unspecified whether this case was easier or pruned.</ref> appear to be in the same category.)

The machine behaves as a double counter in base 2; at key steps, the left and right tapes are and must be mirror images (aside from a terminal "1" on the right).
It's easily proven infinite as follows by forward analysis: we can define a CFL [https://en.wikipedia.org/wiki/Context-free_language] where <L> shows the rule "0(11)*1B1 -> (11)*1C>", and <M> is a [[Closed Set|closed language]] for the TM:
<pre>
<L> ::= 0(11)*(1B1|D10)
| 0(11)*(1E1|E11)(11)*00
| E0(11)*00
| 1A00|11B0
| (1A11|10F1)(11)*00
| 100(11)*(C11|1C1)(11)*00
| 100(11)*C00
| 10B010|101C10|1011C0|101B11|10D101|1E0001|11A001|111B01|1111C1
| 10<L>10
| 10(11)*(1C10|11C0)
| 1<L>1
| 1(11)*1C1

<M> ::= A0|1B0
| (11)*11C0
| <L>1
| (11)*1(C1|1C0)
</pre>

In particular, <L> includes 10<L>10 and 1<L>1, but not for example 1<L>10; indeed, a config of the form (1<L>10)1 will halt the TM.
It therefore provides an example of "BB(6, 2, 2)" needing an inductive or closed-language decider stronger than (weighted) finite automata methods.

Note: A simpler multi-symbol example of the phenomenon is https://bbchallenge.org/1RB2LA0LA_1LA2RC0RC_---2RB0RB, with the rule "bin(n) <A reversed(bin(n)) |- bin(n+1) <A reversed(bin(n+1))".

== References ==
<references/>

Bonus Cryptid

2024-08-13T13:58:37Z

DF376:

{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB|undecided}}

[[BB(2,5)]] [[Cryptid]] found by Daniel Yuan.

See https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid<nowiki/>{{Machine|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB}}
[[Category:Cryptids]]
[[Category:Stub]]

Beaver Math Olympiad

2024-08-13T13:39:22Z

DF376: /* Solved problems */

'''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 every non-essential details (e.g. 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 ==

=== {{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>.

=== [[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]])

== Solved problems ==

=== {{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

=== {{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>

Beaver Math Olympiad

2024-08-13T13:36:31Z

DF376: /* Unsolved problems */

'''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 every non-essential details (e.g. 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 ==

=== {{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>.

=== [[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]])

== Solved problems ==

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

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

=== {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB}} ===

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>

Translated cycler

2024-08-13T13:34:48Z

DF376: /* Infinite shift rule */

[[File:Translated_cycler_44394115_annotated.svg|right|thumb|Example "Translated cycler": 45-step space-time diagram of bbchallenge's machine {{TM|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC}}. The same bounded pattern is being translated to the right forever. The text annotations illustrate the main idea for recognising "Translated Cyclers": find two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state (here state D) such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.]]

A '''translated cycler''' (also known as a '''partial recurrent''' or '''Lin recurrent''' TM) is a non-halting [[Turing machine]] which eventually exhibits a traveling cyclic behavior. Specifically, a TM has ented a translated cycle once it begins repeating a fixed sequence of transition rules in such a way that it will continue repeating them forever. It is, by far, the most common type of non-halting behavior. For example, 95% of all infinite [[BB(6)]] TMs are translated cyclers (which have cycled at least once within the first 1000 steps) and this number is relatively consistent across other BB "domains" (Say BB(5), BB(3,3), etc.).

== History ==
Translated cycling behavior was first described by Shen Lin in his proof of [[BB(3)]] where he called it "partial recurrence".<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. <nowiki>https://doi.org/10.1145/321264.321270</nowiki></ref> He describes an algorithm for detecting it which appears to be the first documented example of a [[decider]]. This behavior has been given many names over the years. For example, Nick Drozd calls this Lin recurrence in honor of Shen Lin.<ref>Nick Drozd. 2021. [https://nickdrozd.github.io/2021/02/24/lin-recurrence-and-lins-algorithm.html Lin Recurrence and Lin's Algorithm]</ref>

== Record breaking ==
One way to detect translated cycling is by analyzing [[record breaking]] configurations. This is the algorithm used by [[bbchallenge]]. A Turing machine is a translated cycler if it has two configurations that break a record (i.e. visit a memory cell that was never visited before) in the same state such that the content of the memory tape at distance L from the record positions is the same in both record configurations. Distance L is defined as being the maximum distance to record position 1 that was visited between the configuration of record 1 and record 2.

Here are the properties of the translated cycler shown in the figure:

* L = 2. After the translated cycler reaches record 1, the translated cycler moves at most L = 2 symbols to the left.
* The '''cycle period''' is 10 steps. This is the number of steps from record 1 to record 2.
* The '''cycle offset''' is 2 symbols to the right. In other words, after each cycle, the TM moves 2 places to the right.
* The '''cycle start time''' is 6 steps. This is the position of record 1.

Translated cyclers are close to [[Cycler|Cyclers]] in the sense that they are only repeating a pattern but there is added complexity as they are able to translate the pattern in space at the same time, hence the decider for Cyclers cannot directly apply here.

== Infinite shift rule ==
A translated cycle can be seen as an infinite [[shift rule]]. For example, consider the TM {{TM|1RB0RE_0LC1RC_0RD1LA_1LE---_1LB1RC|non-halt}} in the image at the right. It performs the following [[transition rule]]:

<math display="block">10 \; \textrm{D>} \; 00 \xrightarrow{10} 00 \; 10 \; \textrm{D>}</math>

which can be repeated to form the shift rule:

<math display="block">10 \; \textrm{D>} \; {00}^n \xrightarrow{10n} {00}^n \; 10 \; \textrm{D>}</math>

Furthermore, on step 6, this TM is in config

<math display="block">0^\infty \; 1 \; 10 \; \textrm{D>} \; 0^\infty</math>

Therefore, we can see that for all <math>n \ge 0</math> we can apply the shift rule and so this TM can never halt.

== Notable translated cyclers ==

[[Skelet 1]] is a translated cycler that has a period of 8,468,569,863 steps, an offset of 107,917 symbols to the right, and a start time of at least <math>10^{24}</math>.

== Sources ==
<references />

1RB1LF 1LB1LC 1RD0LE ---0RB 0RC0LA 1RC0RF

2024-08-13T13:34:05Z

DF376:

{{machine|1RB1LF_1LB1LC_1RD0LE_---0RB_0RC0LA_1RC0RF}}{{TM|1RB1LF_1LB1LC_1RD0LE_---0RB_0RC0LA_1RC0RF|undecided}}

This is a chaotic-looking TM in [[BB(6)]] holdouts. It's suspected to be a translated cycler with high period and very hard to accelerate, because many other similar looking TMs become translated cycler in 2e10 steps.

[[Category:Stub]]

1RB2LA0LA 2LC---2RA 0RA2RC1LC

2024-08-13T13:33:35Z

DF376:

{{machine|1RB2LA0LA_2LC---2RA_0RA2RC1LC}}
{{TM|1RB2LA0LA_2LC---2RA_0RA2RC1LC|undecided}}

On July 22, 2024, busycoq received a proof that this TM doesn't halt: https://github.com/meithecatte/busycoq/commit/ce2f22e1616632924622016d9cbb8ba0847b2c6a
[[Category:Stub]]

Champions

2024-08-13T13:32:56Z

DF376:

Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].

== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem.
{| class="wikitable"
|+
!
!Runtime
!Champions
!Comment
|-
|[[BB(2)]]
|6
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Discovered and proven by hand by Tibor Radó
|-
|[[BB(3)]]
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|-
|[[BB(4)]]
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Discovered and proven by Allen Brady
|-
|[[BB(5)]]
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Discovered by Heiner Marxen & Jürgen Buntrock in 1989
Proven by [[bbchallenge.org]] in 2024
|-
|[[BB(6)]]
|<math>> 10 \uparrow\uparrow 15</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|Discovered by Pavel Kropitz in 2022
|-
|[[BB(7)]]
|
|
|
|-
|BB(8)
|
|
|
|-
|BB(9)
|<math>> 10 \uparrow\uparrow 30</math>
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG|halt}}
|Designed by Milton Green in 1964 ([[Green's machines]])
|-
|BB(10)
|<math> > 10 \uparrow\uparrow 10^{10^{12}} </math>
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH|halt}}
|[[Green's machines]]
|-
|BB(11)
|<math> > 10 \uparrow\uparrow\uparrow 10^{12} </math>
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI|halt}}
|[[Green's machines]]
|-
|BB(12)
|<math> > 2 \uparrow^{12} 4 > Ack(11) </math>
|{{TM|1RB1LL_0RC1RC_1LD1LG_0RE1LC_1LD1RF_1RE1RI_1RH0LA_---0RF_0RB1LJ_---0LK_0LF1LF_1RZ0LA|halt}}
|[https://github.com/sligocki/sligocki.github.io/issues/7#issuecomment-2143486164 Compilation] of a BB(3,4) TM by <code>@Iijil1</code> in 2024
|-
|BB(13)
|<math> > Ack(2045) </math>
|
|[https://googology.fandom.com/wiki/User:Wythagoras/Rado%27s_sigma_function/BB(13) Designed] by <code>@Wythagoras</code> in 2016
|-
|BB(14)
|<math> > Ack(10 \uparrow\uparrow 5) </math>
|
|[[User:Jacobzheng|Designed]] by <code>Jacobzheng</code> in 2024
|-
|BB(15)
|
|
|
|-
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) > g_{64} </math>
|
|Designed by Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "B(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
|}

== References ==
<references />

Green's machines

2024-08-13T13:31:13Z

DF376:

In 1964, Milton W. Green hand-crafted a family of fast-growing Turing Machines with n-states, 2-symbols for all <math>n \ge 4</math>.<ref>Milton W. Green. “A Lower Bound on Rado’s Sigma Function for Binary Turing Machines”, ''Proceedings of the IEEE Fifth Annual Symposium on Switching Circuits Theory and Logical Design'', 1964, pages 91–94, [https://doi.org/10.1109%2FSWCT.1964.3 https://doi.org/10.1109/SWCT.1964.3]</ref> This family grows roughly as fast as the Ackermann function<math display="block">BB_{2n} \approx 3 \uparrow^{n-2} 3</math>

== Machines ==
{| class="wikitable"
|+
!# States
!TM
!Sigma Score
|-
|4
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1RD1RA|halt}}
|7
|-
|5
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1RE1RC|halt}}
|13
|-
|6
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1RF1RD|halt}}
|35
|-
|7
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1RG1RE|halt}}
|22,961
|-
|8
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1RH1RF|halt}}
|<math> \frac{7 \cdot 3^{93} - 3}{2} </math>
|-
|9
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1RI1RG|halt}}
|<math> > 3 \uparrow\uparrow 31 </math>
|-
|10
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1RJ1RH|halt}}
|<math> > 3 \uparrow\uparrow 3 \uparrow\uparrow 4 </math>
|-
|11
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1RK1RI|halt}}
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 2 </math>
|-
|12
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1RL1RJ|halt}}
|<math> > 3 \uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow 4 </math>
|-
|13
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1RM1RK|halt}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 2 </math>
|-
|14
|{{TM|1LB1RZ_0LC1LC_0LD0LC_1LE1RA_0LF0LE_1LG1RD_0LH0LG_1LI1RF_0LJ0LI_1LK1RH_0LL0LK_1LM1RJ_0LN0LM_1RN1RL|halt}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow 4 </math>
|-
|15
|{{TM|1LD1LB_1LZ1LA_0LB1LD_0LE0LD_1LF1RC_0LG0LF_1LH1RE_0LI0LH_1LJ1RG_0LK0LJ_1LL1RI_0LM0LL_1LN1RK_0LO0LN_1RO1RM|halt}}
|<math> > 3 \uparrow\uparrow\uparrow\uparrow\uparrow 3 \uparrow\uparrow\uparrow\uparrow\uparrow 2 </math>
|
|}

== External Links ==

* Shawn Ligocki. Green's Machines. 2023. https://www.sligocki.com/2023/10/19/greens-machines.html

== References ==
<references />

1RB0RE 0RC--- 1LD1LE 1LE1LD 1RF0LC 1RA1RF

2024-08-13T13:29:04Z

DF376:

{{machine|1RB0RE_0RC---_1LD1LE_1LE1LD_1RF0LC_1RA1RF}}
{{TM|1RB0RE_0RC---_1LD1LE_1LE1LD_1RF0LC_1RA1RF|undecided}}

mxdys — 11 Jul 2024 at 7:10 AM ET

<pre>
1RB0RE_0RC---_1LD1LE_1LE1LD_1RF0LC_1RA1RF (chaotic 1dCA in bell)

(...0 a1 a2 ... an > b1 b2 ... bm 0...) := (0^inf 0 1^a1 0 1^a2 ... 0 1^an E> 1^b1 0 1^b2 0 ... 1^bm 0 0^inf)
(...0 a1 a2 ... an < b1 b2 ... bm 0...) := (0^inf 0 1^a1 0 1^a2 ... 0 1^an <E 1^b1 0 1^b2 0 ... 1^bm 0 0^inf)

start from:
...0 1 < 2 0...

local rewrite rules:
a > 0 b c+1
----------- (R)
a+b+2 0 > c

a > b+2
--------- (RL)
a+1 < b+1

a > 1 0...
---------- (RL'')
a+1 < 0...

a 2b+1 <
--------- (L)
< a+2 1^b

2a <
------- (LR)
> 0 1^a

a > 0 b 0...
-------------- (RL')
a+b+3 < 2 0...
</pre>

are these rules closed? it's likely to halt if these rules are not closed.

[[Category:Stub]]

Adjacent

2024-08-13T13:28:26Z

DF376:

Two Turing machines are '''adjacent''' if you can get from one to the other by modifying only one transition and (optionally) applying a [[permutation]]. Adjacent TMs are useful to think about at times because they can have similar behavior or follow similar rules. This is definitely not true for all adjacent TMs, but it is in some cases.

== Examples ==
A good example of adjacent TMs are the 5 [[BB(5)]] [[Shift overflow counter|shift overflow counters]] from [[Skelet's 43 holdouts]]:<ref>Shawn Ligocki. Shift Overflow Counters. 2023. https://www.sligocki.com/2023/02/05/shift-overflow.html</ref>
{| class="wikitable"
!Name
!Machine
|-
|<code>sk15</code>
|{{TM|1RB---_1RC1LB_1LD1RE_1LB0LD_1RA0RC|non-halt}}
|-
|<code>sk26</code>
|{{TM|1RB1LD_1RC0RB_1LA1RC_1LE0LA_1LC---|non-halt}}
|-
|<code>sk33</code>
|{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RE|non-halt}}
|-
|<code>sk34</code>
|{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA|non-halt}}
|-
|<code>sk35</code>
|{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA|non-halt}}
|}
All of these TMs are adjacent to <code>sk33</code> via the following changes:
{| class="wikitable"
!Name
!Change from <code>sk33</code>
!Start State
!Before Permutation
!TNF
|-
|<code>sk34</code>
|<code>E1 -> 1RA</code>
|<code>A</code>
|<code>1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA</code>
|<code>1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA</code>
|-
|<code>sk35</code>
|<code>E1 -> 0LA</code>
|<code>A</code>
|<code>1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA</code>
|<code>1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA</code>
|-
|<code>sk26</code>
|<code>B0 -> 1RE</code>
|<code>A</code>
|<code>1RB1LC_1RE0RB_1LD0LA_1LE---_1LA1RE</code>
|<code>1RB1LD_1RC0RB_1LA1RC_1LE0LA_1LC---</code>
|-
|<code>sk15</code>
|<code>B0 -> 1RE</code>
|<code>D</code>
|<code>1RB1LC_1RE0RB_1LD0LA_1LE---_1LA1RE</code>
|<code>1RB---_1RC1LB_1LD1RE_1LB0LD_1RA0RC</code>
|}
For <code>sk34</code> and <code>sk35</code> the adjacency is easy to see because there is no permutation of states.

== Tools ==
<code>Code/Adjacent.py</code> in https://github.com/sligocki/busy-beaver can be used to list all adjacent TMs.

== References ==
<references />

Permutation

2024-08-13T13:27:13Z

DF376:

Turing machine A is a '''permutation''' of Turing machine B if they are isomorphic up to permuting (renaming) states, symbols (aside from the blank symbol) and directions. If the start state is not affected by the permutation, then the two TMs are functionally identical and are represented by a single TM in [[TNF]]. If the start state is changed, then TM A is functionally identical to TM B started in a different start state. Therefore we can say that an n-state TM has effectively n permutations (or n TNF permutations) one for each choice of start state.

Identifying permutations is very useful during TM analysis, since permutations of a TM tend to have the same behavior aside from precise starting configuration. For example, any [[Inductive rule|inductive rules]] or [[Closed Set|closed set]] proven about the original TM will also apply to the permutation (as long as the permutation TM enters that closed set or rule starting config).

== Example ==
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} permuted to start state C is {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---|undecided}}. Here the permutation is <math>A \to B \to C \to A</math>, <math>1 \leftrightarrow 2</math> and <math>L \leftrightarrow R</math>. For example, the first instruction of the original TM <code>A0 -> 1RB</code> becomes <code>B0 -> 2LC</code> in the second TM.

== Tools ==
<code>Code/Permute.py</code> in <nowiki>https://github.com/sligocki/busy-beaver</nowiki> can be used to list all permutations of a TM.

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2024-08-13T13:25:46Z

DF376:

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}}{{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}

This is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If can be proven to halt, it will be the BB(3,3) champion. However, it could also turn out to be probviously halting [[Cryptid]].

This is holdout #758 on Justin's 3x3 mugshots. And if you start in state C it is a [[permutation]] of #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. It simulates a complex set of Collatz-like rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely".

NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.

== dyuan01's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

<pre>
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf
</pre>

{| class="wikitable"
! From !! To
|-
| A1(0, b, 2n) || A2(1, b+2n+1, 0)
|-
| A1(0, b, 2n+1) || A1(1, 0, b+2n+3)
|-
| A1(m+1, b, 0) || A1(m, 0, b+2)
|-
| A1(m+1, b, n+1) || A2(m, b+1, n)
|-
| A2(0, b, 2n) || A1(2b+3, 0, 2n+1)
|-
| A2(0, b, 2n+1) || A2(2b+3, 2n+1, 0)
|-
| A2(m+1, b, 0) || B(m, b+2)
|-
| A2(m+1, b, n+1) || A1(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A2(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A1(m, 0, 2n+3)
|}
Starting from A1(0, 0, 1) (at step 2).

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code>

<pre>
(0, b, n) -> (2b+2, 1, n) if n is even
-> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
-> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
-> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
-> Halt if n is odd

(2, b, 1) -> Halt if b is even
-> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)
</pre>

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

<pre>
step (A2 0 b n) | even n = A2 (2*b+2) 1 n
| otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
| otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
| otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
| otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated
</pre>

== Shawn's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

<pre>
(0, b, 2c) -> (2b+2, 1, 2c)

(1, b, 0) -> Halt
(1, 2b, 2c) -> (0, 1, 2(b+c+1))
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))

(a, 2b, 0) -> (a-2, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2b+6)
(a, 2b+1, 0) -> (a-3, 1, 2b+4)

(a, b, c) -> (a-2, b+3, c-2)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
Even Phase: a,c even:
(0, b, 2c) -> (2b+2, 1, 2c)
(2a+2, 2b, 0) -> (2a, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2(b+3))

To Odd Phase:
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)

Odd Phase: a odd, c even
To Halt:
(1, b, 0) -> Halt
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt

To Even Phase:
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))

(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)
</pre>

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

== Repeated (0, b, 2c) ==

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>

Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

== Repeated (0, 1, 2c) ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>

<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>

And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.

And as n gets way bigger, these ranges of repeat will increase exponentially.

1RB1RA 1LC0RE 0LF1LD 1LA1LC 1RA1RB ---0LD

2024-08-13T13:24:48Z

DF376:

{{machine|1RB1RA_1LC0RE_0LF1LD_1LA1LC_1RA1RB_---0LD}}
{{TM|1RB1RA_1LC0RE_0LF1LD_1LA1LC_1RA1RB_---0LD|halt}}

Analysis by [[User:sligocki|Shawn Ligocki]]:

<pre>
B(a, b) = $ 101^a 10^b <C 1^3 $

B(0, 3b) -> Halt(8b+4)
B(a+1, 3b) -> B(a, 4b+5)
B(a, 3b+1) -> B(a+1, 4b+2)
B(a, 3b+2) -> B(a, 8b+10)

Start --(13)--> B(0, 2)
</pre>

This performs an unbiased pseudo-random walk. Unbiased random walks have 100% chance to return to 0. This TM eventually does, but only after 34,821 iterations (reaching <math>a = 162</math>).

<pre>
Code/Quick_Sim.py 1RB1RA_1LC0RE_0LF1LD_1LA1LC_1RA1RB_---0LD -n6 --print-loops=100_000
...
Steps: ~10^15_713.71342
Nonzeros: ~10^7_857.11327
</pre>

Antihydra

2024-08-13T13:23:44Z

DF376:

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}
[[File:Antihydra-depiction.png|right|thumb|Artistic depiction of Antihydra by Jadeix]]
'''Antihydra''' is the 6-state 2-symbol machine {{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}.

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>
 
starting from <math>A(8, 0)</math>, using configurations of the form <math>A(a+4, b) = 0^\infty \; 1^b \; 0 \; 1^a \; E> \; 0^\infty</math>.<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>

It was discovered by mxdys on 28 Jun 2024 and shared on Discord.<ref>[https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message], accessed 30 June 2024.</ref>

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).<ref>[https://discord.com/channels/960643023006490684/1026577255754903572/1256403772998029372 Discord message], accessed 2 July 2024.</ref>

== Simulator ==

Antihydra is based on a [[consistent Collatz]] sequence, and as such, its behaviour can be simulated efficiently via using the techniques written in that article.

Two older simulators are available (that are much slower for calculating large numbers of elements due to running in <math>O(n^2)</math> rather than quasilinear time, but may be useful in cases where more detail is needed about each element or where only a relatively small number of elements is needed):

A fast simulator written in Rust for the odd/even sequence used by Antihydra is available [http://nethack4.org/esolangs/fasthydra.zip here].

Alternatively, 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.

==Sources==
<references />

[[Category:Individual machines]]
[[Category:Cryptids]]

Hydra

2024-08-13T13:23:03Z

DF376:

{{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved|Does Hydra run forever?}}{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}}
'''Hydra''' is a [[BB(2,5)]] machine that simulates the [[Collatz-like]] iteration

<math display="block">\begin{array}{l}
C(2a+1, & b) & \to & A(3a+1, & b+2) \\
C(2a, & b) & \to & A(3a, & b-1) & \text{if} & b>0 \\
C(2a, & 0) & \to & \text{HALT}
\end{array}</math>
 
starting from <math>C(3,0)</math>, using configurations of the form <math>C(a+2,b) = 0^\infty \; .<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2023). Accessed 22 July 2024.</ref>

It is closely related to the machine [[Antihydra]].<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>

The sequence calculated by Hydra is a [[consistent Collatz]] sequence, (which implies, among other things, that its odd/even pattern can be calculated in quasilinear time). In the first 60 million elements, there are 29995836 even values of <code>a</code> and 30004165 odd values; thus, is known that Hydra cannot halt within the first 90 million Collatz iterations.

An older simulator for the odd/even sequence used by Hydra is available [http://nethack4.org/esolangs/fasthydra.zip here], but it runs in <math>O(n^2)</math> time and thus is unusably slow compared to the consistent Collatz simulation approach.

== Name ==

The name ''Hydra'' references the Ancient Greek legend: just as the legendary creature was growing 2 heads after losing 1 head, the ''b'' counter that is kept on the right side of the tape either increases by 2 or decreases by 1 (approximately with equal frequency if modelled as a random process; in reality it depends on the parity of ''a''). The Hydra dies (halts) when the last head is cut.

==Sources==
<references/>

[[Category:Stub]]
[[Category:Cryptids]]

1RB1RE 1LC0RA 0RD1LB ---1RC 1LF1RE 0LB0LE

2024-08-13T13:22:33Z

DF376:

{{machine|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE}}{{unsolved|Does this TM run forever?}}{{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}

A [[BB(6)]] TM which is modeled by

<pre>
A(a, b) -> A(a-b, 4b+2) if a > b
A(a, b) -> A(2a+1, b-a) if a Halt if a = b

Start A(1, 2)
</pre>

for <code>A(a, b) = 0^inf 10^{a-1} 0 1^b E> 0^inf</code>. The configuration is always valid because <math>a \ge 1</math> is always maintained. It is a possible [[Cryptid]] since it seems hard to predict whether we could ever end up in <code>A(n, n)</code>, but investigations are ongoing on Discord as of 27 Jun 2024.

== Analysis from Discord ==
@-d [https://discord.com/channels/960643023006490684/1026577255754903572/1255047256688824390 25 Jun 2024 2:29 AM ET]:
<pre>
Let f(a,b) represent (10)^a D> 1^b. By inspection, the machine visits f(0,3) f(2,2) f(1,7) f(4,5) f(0,19) f(2,18) f(6,15) f(14,8).

I got these rules for f(a,b) and verified them up to 0<=a<=100 and 1<=b<=100.
f(a,b) -> f(a-b+1,4b-1) if b < a+2
f(a,a+2) -> halt
f(a,b) -> f(2a+2,b-a-1) if b > a+2

I ran these rules from f(0,3) and gave up after reaching a,b > 2^1000000. It looks like halting becomes less and less likely. Is there a way to show this runs forever (or miraculously halts)?
</pre>

@Shawn Ligocki — [https://discord.com/channels/960643023006490684/1026577255754903572/1255371132694167591 25 Jun 2024 at 11:56 PM ET]:
<pre>
I can confirm roughly the same rules (I chose a slightly different standard config):
1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE

E(a, b, c) = 0^inf 10^a 0 10^b 1^c E> 0^inf

Base Rules:
E(a+1, b, c+2) -> E(a, b+2, c+1)
E(a+1, b, 1) -> E(a, 0, 2b+6)
E(0, b, c+2) -> E(b+2, 0, c+1)
E(0, b, 1) -> Halt(b+4)

High-level Rules:
E(a, 0, c+1) --> E(a-c-1, 0, 4c+6) if a > c
E(a, 0, c+1) --> E(2a+2, 0, c-a) if a < c
E(a, 0, c+1) --> Halt(2c+4) if a = c

Connecting to your notation @-d : f(a, b+2) -> E(a, 0, b+1)
</pre>

@Shawn Ligocki — 26 Jun 2024 at 12:25 AM
<pre>
Hm, this is interesting. I decided to track "spread" akin to what @savask and I have been looking at for the similar 3x3 TM we're looking at in ⁠bbxy . Here I define spread = abs(a - c) in config E1(a, c) = E(a, 0, c+1). Here's the results I have so far:
1 E1(2, 0) spread: [2, 2] (0.06s)
100_001 E1(10^6_557, 10^6_555) spread: [1, 10^6_557] (0.44s)
200_001 E1(10^13_124, 10^13_125) spread: [10^6_557, 10^13_125] (1.27s)
300_001 E1(10^19_670, 10^19_669) spread: [10^13_123, 10^19_670] (2.52s)
400_001 E1(10^26_235, 10^26_237) spread: [10^19_668, 10^26_237] (4.23s)
500_001 E1(10^32_799, 10^32_799) spread: [10^26_235, 10^32_799] (6.39s)
600_001 E1(10^39_350, 10^39_352) spread: [10^32_799, 10^39_352] (8.98s)
700_001 E1(10^45_930, 10^45_930) spread: [10^39_350, 10^45_930] (12.06s)
800_001 E1(10^52_486, 10^52_486) spread: [10^45_929, 10^52_486] (15.54s)
900_001 E1(10^59_046, 10^59_047) spread: [10^52_485, 10^59_047] (19.57s)
1_000_001 E1(10^65_613, 10^65_612) spread: [10^59_045, 10^65_613] (24.05s)
1_100_001 E1(10^72_154, 10^72_153) spread: [10^65_609, 10^72_154] (28.92s)
1_200_001 E1(10^78_728, 10^78_729) spread: [10^72_153, 10^78_729] (34.21s)
1_300_001 E1(10^85_288, 10^85_289) spread: [10^78_729, 10^85_289] (40.03s)
1_400_001 E1(10^91_830, 10^91_829) spread: [10^85_288, 10^91_829] (46.40s)
1_500_001 E1(10^98_394, 10^98_393) spread: [10^91_829, 10^98_394] (53.11s)
1_600_001 E1(10^104_961, 10^104_959) spread: [10^98_393, 10^104_961] (60.18s)
1_700_001 E1(10^111_523, 10^111_523) spread: [10^104_958, 10^111_523] (67.75s)
1_800_001 E1(10^118_088, 10^118_088) spread: [10^111_523, 10^118_088] (75.77s)
1_900_001 E1(10^124_631, 10^124_630) spread: [10^118_088, 10^124_631] (84.39s)
2_000_001 E1(10^131_185, 10^131_185) spread: [10^124_630, 10^131_185] (93.41s)
...
3_000_001 E1(10^196_733, 10^196_733) spread: [10^190_163, 10^196_733] (217.87s)

Here spread: [X, Y] means that the spread values (since last print) had min X, max Y
So notice that the spread is basically uniformly increasing. In fact these [X, Y] intervals hardly even overlap!
That makes me think there's something about this that makes small spread impossible (and thus halt impossible)
Or that it's like Bigfoot and it ... could go back to zero, but the chances are infinitesimal!
</pre>

savask — 26 Jun 2024 at 1:02 AM
<pre>
Maybe we can simplify a little bit more. Set (a, c) = E(a, 0, c+1) then the rules are
(a, c) -> (a-c-1, 4c+5) if a > c
(a, c) -> (2a+2, c-a-1) if a < c
(a, c) -> Halt if a = c

I like that this way they are more symmetrical with a-c-1 vs c-a-1
</pre>

Shawn Ligocki — 26 Jun 2024 at 2:33 AM
<pre>
FWIW, there is a value x ~= 1.76 such that as c -> inf: (xc, c) -> (xyc, yc) via path "rll" (right->0 [ie a > c], left->0 [ie a < c], left->0). Which would repeat forever if it were exact, but it is an unstable cycle so any slight deviation and it gets further and further away, so that doesn't seem like a reasonable proof direction :/
</pre>dyuan01 — 26 Jun 2024 at 2:32 PM
If we let A(a, c) = (a-1, c-1), we can get these rules:
```
A(a, c) -> A(a-c, 4c+2) if a > c
A(a, c) -> A(2a+1, c-a) if a < c
A(a, c) -> Halt if a = c
```
And we start with (1, 2)

I'm not sure if it even helps, but at least the rules look slightly more "human-manageable"

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2024-08-13T13:19:51Z

DF376:

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}}{{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|non-halt}}

This is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If can be proven to halt, it will be the BB(3,3) champion. However, it could also turn out to be probviously halting [[Cryptid]].

This is holdout #758 on Justin's 3x3 mugshots. And if you start in state C it is a [[permutation]] of #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. It simulates a complex set of Collatz-like rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely".

NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.

== dyuan01's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

<pre>
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf
</pre>

{| class="wikitable"
! From !! To
|-
| A1(0, b, 2n) || A2(1, b+2n+1, 0)
|-
| A1(0, b, 2n+1) || A1(1, 0, b+2n+3)
|-
| A1(m+1, b, 0) || A1(m, 0, b+2)
|-
| A1(m+1, b, n+1) || A2(m, b+1, n)
|-
| A2(0, b, 2n) || A1(2b+3, 0, 2n+1)
|-
| A2(0, b, 2n+1) || A2(2b+3, 2n+1, 0)
|-
| A2(m+1, b, 0) || B(m, b+2)
|-
| A2(m+1, b, n+1) || A1(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A2(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A1(m, 0, 2n+3)
|}
Starting from A1(0, 0, 1) (at step 2).

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code>

<pre>
(0, b, n) -> (2b+2, 1, n) if n is even
-> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
-> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
-> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
-> Halt if n is odd

(2, b, 1) -> Halt if b is even
-> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)
</pre>

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

<pre>
step (A2 0 b n) | even n = A2 (2*b+2) 1 n
| otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
| otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
| otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
| otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated
</pre>

== Shawn's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

<pre>
(0, b, 2c) -> (2b+2, 1, 2c)

(1, b, 0) -> Halt
(1, 2b, 2c) -> (0, 1, 2(b+c+1))
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))

(a, 2b, 0) -> (a-2, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2b+6)
(a, 2b+1, 0) -> (a-3, 1, 2b+4)

(a, b, c) -> (a-2, b+3, c-2)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
Even Phase: a,c even:
(0, b, 2c) -> (2b+2, 1, 2c)
(2a+2, 2b, 0) -> (2a, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2(b+3))

To Odd Phase:
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)

Odd Phase: a odd, c even
To Halt:
(1, b, 0) -> Halt
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt

To Even Phase:
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))

(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)
</pre>

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

== Repeated (0, b, 2c) ==

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>

Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

== Repeated (0, 1, 2c) ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>

<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>

And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.

And as n gets way bigger, these ranges of repeat will increase exponentially.

1RB0LD 1RC0RF 1LC1LA 0LE1RZ 1LF0RB 0RC0RE

2024-08-13T13:14:58Z

DF376:

{{machine|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}

Current [[BB(6)]] Champion. Discovered by Pavel Kropitz on 30 May 2022. This TM runs for over 10↑↑15 steps. See analysis: [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15].

It simulates the following Collatz-like rules starting at C(5):

<math display="block">\begin{array}{l}
C(4k) & \to & Halt(\frac{3^{k+3} - 11}{2}) \\
C(4k+1) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+2) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+3) & \to & C(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>
[[Category:Stub]]

1RB0LD 1RC0RF 1LC1LA 0LE1RZ 1LF0RB 0RC0RE

2024-08-13T13:14:19Z

DF376:

{{machine|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}

Current [[BB(6)]] Champion. Discovered by Pavel Kropitz on 30 May 2022. This TM runs for over 10↑↑15 steps. See analysis: [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15].

It simulates the following Collatz-like rules starting at C(5):

<math display="block">\begin{array}{l}
C(4k) & \to & Halt(\frac{3^{k+3} - 11}{2}) \\
C(4k+1) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+2) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+3) & \to & C(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>
[[Category:Stub]]

1RB0RC 1LC1LF 1RD0LB 1RZ0LE ---1RA 1LB0RE

2024-08-13T13:13:30Z

DF376:

{{machine|1RB0RC_1LC1LF_1RD0LB_1RZ0LE_---1RA_1LB0RE}}{{TM|1RB0RC_1LC1LF_1RD0LB_1RZ0LE_---1RA_1LB0RE|halt}}

BB6 (with one unfilled transition) score/sigma champion. This machine does something sort of similar to [[1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_1RZ0LE]], but with A(a, 3k+r, c) -> A(a+4k, r, c) instead of the C(a, 3k+r, c) -> C(a, r, c+2k) above, so it gets about 2x tape size.

<pre>
1RB0RC_1LC1LF_1RD0LB_1RZ0LE_---1RA_1LB0RE

Steps: ~10^13.15788 = 14_384_000_997_114
Nonzeros: 4_059_761 = 4_059_761

A(a, b, c) = $ 01^a A> 1^b 0 1^c $

A(a, b+3, c) -> A(a+4, b, c) if a >= 1

A(a, 0, 0) -> A(2, 2a-1, 1) if a >= 1
A(a, 0, c+1) -> A(a+1, c, 0)
A(a, 2, c) -> A(2, 2a+5, c+1)

A(a, 1, 0) -> Halt(a+2)
A(a, 1, 1) -> A(2, 2a+1, 1)
A(a, 1, 2) -> A(2, 2a+3, 1)
A(a, 1, 3) -> Halt(a+4)
A(a, 1, c+4) -> A(a+5, 0, c)

@20: A(2, 1, 2)

0 A( 2, 1, 2)
1 A( 2, 7, 1)
2 A( 2, 21, 1)
3 A( 31, 0, 0)
4 A( 2, 61, 1)
5 A( 2, 165, 1)
6 A( 223, 0, 0)
7 A( 2, 445, 1)
8 A( 2, 1_189, 1)
9 A( 2, 3_173, 1)
10 A( 2, 8_465, 2)
11 A( 2, 22_577, 3)
12 A( 2, 60_209, 4)
13 A( 2, 160_561, 5)
14 A( 214_087, 0, 1)
15 A( 214_088, 0, 0)
16 A( 2, 428_175, 1)
17 A( 570_903, 0, 0)
18 A( 2, 1_141_805, 1)
19 A( 2, 3_044_817, 2)
20 A( 4_059_759, 1, 0)
Halted: 20 4_059_761
</pre>Analysis by [[User:sligocki]].

1RB1RA 1LC1RF 1RE1LD 0RD1LB ---0RA 1RZ0LE

2024-08-13T13:12:26Z

DF376:

{{machine|1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_1RZ0LE}}{{TM|1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_1RZ0LE|halt}}

AFAICT this is the current BB6 (with one unused transition) step champion.

<pre>
1RB1RA_1LC1RF_1RE1LD_0RD1LB_---0RA_1RZ0LE

Steps: ~10^13.39223 = 24_673_582_891_560
Nonzeros: 2_323_223 = 2_323_223

C(a, b, c) = $ 1^a 0 1^b <C 1^2c+1 $

C(a, b+3, c) -> C(a, b, c+2)

C(a, 0, c) -> C(a+1, 2c+1, 0)
C(a, 1, c) -> C(0, a, c+1)

C(0, 2, c) -> C(1, 2c+4, 0)
C(1, 2, c) -> C(1, 2c+6, 0)
C(2, 2, c) -> C(1, 2c+7, 0)
C(a+3, 2, c) -> 1^a 01^c+3 11 Z>

Start: @2: C(0, 1, 0)
</pre>

It does one of these interesting Collatz Markov Chains where it only halts if <math>a \geq 3</math> and <math>b \bmod 3 = 2</math> and otherwise has a couple ways to reset <math>a \leq 1</math>. But eventually after flipping that coin 62 times it finally halts.

Analysis by [[User:sligocki]].

Inductive Proof System

2024-08-13T13:11:17Z

DF376: /* Bouncer */

An '''Inductive Proof System''' is an [[Accelerated Simulator]] and [[Decider]] which operates by automatically detecting and proving [[Transition rule|transition rules]] using Mathematical Induction.

== Inductive Rule ==
An inductive rule is a general transition rule (a start and end configuration, generalized with variables for repetition counts) along with a proof. The proof generally has two pieces: the base case and the inductive case. Each is a list of steps where each step is (A) a specific TM transition, (B) an application of the inductive hypothesis, (C) an application of a previously defined rule.

=== Rule Levels ===
We can assign levels to any Inductive Rule. A Level 0 (L0) rule does not depend on any previously defined inductive rules. A Level 1 (L1) rule depends only upon previously proven L0 rules, etc. All L0 Rules (which only invoke the inductive hypothesis once) are [[Shift rule|Shift rules]].

== Example Proofs ==

=== Notation ===
In this article we will use the following notation for an Inductive Rule and its proof:

<math>P(n)</math>

* Proof by induction on n:
** Base case: ''List of steps to prove the base case <math>P(0)</math>. Often this is the empty list since <math>P(0)</math> is trivially true (in zero steps).''
** Inductive case: ''List of steps to prove <math>P(n+1)</math> of which some can be "IH" the inductive hypothesis that <math>P(n)</math>.''

=== Bouncer ===
Consider the [[bouncer]] {{TM|1RB0RC_0LC---_1RD1RC_0LE1RA_1RD1LE|non-halt}}. We can prove the following Inductive Rules:

# Shift (L0) Rule: <math>C(n) : \textrm{C>} \; 1^n \to 1^n \; \textrm{C>}</math>
#* Proof by induction on n
#** Base case: []<math display="block">\textrm{C>} \; 1^0 = 1^0 \; \textrm{C>}</math>
#** Inductive case: [C1, IH]<math display="block">\textrm{C>} \; 1^{n+1} \xrightarrow{C1} 1 \; \textrm{C>} \; 1^n \xrightarrow{IH} 1^{n+1} \; \textrm{C>}</math>
# Shift (L0) Rule: <math>E(n) : 1^n \; \textrm{<E} \to \textrm{<E} \; 1^n</math>
#* Proof by induction on n
#** Base case: []
#** Inductive case: [E1, IH]
# L1 Rule: <math>A(n) : \textrm{A>} \; 1^n \; 0^\infty \to 1^{2n} \; \textrm{A>} \; 0^\infty</math>
#* Proof by induction on n
#** Base case: []
#** Inductive case: [A1, C(n), C0, D0, E(n+1), E0, D1, IH]<math display="block">\begin{array}{l}
\\
\textrm{A>} \; 1^{n+1} \; 0^\infty
& \xrightarrow{A1} &
0 \; \textrm{C>} \; 1^n \; 0^\infty \\
& \xrightarrow{C(n)} &
0 \; 1^n \; \textrm{C>} \; 0^\infty \\
& \xrightarrow{C0} &
0 \; 1^{n+1} \; \textrm{D>} \; 0^\infty \\
& \xrightarrow{D0} &
0 \; 1^{n+1} \; \textrm{<E} \; 0^\infty \\
& \xrightarrow{E(n+1)} &
0 \; \textrm{<E} \; 1^{n+1} \; 0^\infty \\
& \xrightarrow{E0} &
1 \; \textrm{D>} \; 1^{n+1} \; 0^\infty \\
& \xrightarrow{D1} &
1^2 \; \textrm{A>} \; 1^n \; 0^\infty \\
& \xrightarrow{IH} &
1^{2(n+1)} \; \textrm{A>} \; 0^\infty \\
\end{array}</math>
# L2 Rule: <math>0^\infty \; 1^a \; \textrm{A>} \; 0^\infty \to 0^\infty \; 1^{2a+6} \; \textrm{A>} \; 0^\infty</math>
#* Proof: [A0, B0, C1, C0, D0, E(a+2), E0, D1, A(a+1)]<math display="block">\begin{array}{l}
\\
0^\infty \; 1^a \; \textrm{A>} \; 0^\infty
& \xrightarrow{A0, B0, C1, C0, D0} &
0^\infty \; 1^{a+2} \; \textrm{<E} \; 0^\infty \\
& \xrightarrow{E(a+2)} &
0^\infty \; \textrm{<E} \; 1^{a+2} \; 0^\infty \\
& \xrightarrow{E0,D1} &
0^\infty \; 1^2 \; \textrm{A>} \; 1^{a+1} \; 0^\infty \\
& \xrightarrow{A(a+1)} &
0^\infty \; 1^{2a+4} \; \textrm{A>} \; 0^\infty \\
\end{array}</math>

We can see now that the last rule can be applied repeatedly forever, so if it is ever applied once, the TM will never halt. In fact, in this case the start config is equal to <math>0^\infty \; 1^0 \; \textrm{A>} \; 0^\infty</math> and thus this TM will never halt.
[[Category:Deciders]]

Bigfoot

2024-08-13T13:10:13Z

DF376:

{{machine|1RB2RA1LC_2LC1RB2RB_---2LA1LA}}{{unsolved|Does Bigfoot run forever?}}{{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|non-halt}}
'''Bigfoot''' is a [[BB(3,3)]] [[Cryptids|Cryptid]]. It simulates the Collatz-like function

<math display="block">\begin{array}{l}
A(a, & 6k, & c) & \to & A(a, & 8k+c-1, & 2) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+1, & c) & \to & A(a+1, & 8k+c-1, & 3) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+2, & c) & \to & A(a-1, & 8k+c+3, & 2) & \text{if} & a \ge 1 \\
A(a, & 6k+3, & c) & \to & A(a, & 8k+c+1, & 5) \\
A(a, & 6k+4, & c) & \to & A(a+1, & 8k+c+3, & 2) \\
A(a, & 6k+5, & c) & \to & A(a, & 8k+c+5, & 3) \\
\end{array}</math>

<math display="block">A(0, 6k+2, c) \to \text{Halt}(16k+2c+7)</math>

starting from <math>A(2, 1, 2)</math>.

It was discovered by Shawn Ligocki on 14 Oct 2023 and shared in the blog post [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is Hard].

[[Category:Stub]]
[[Category:Cryptids]]

5-state busy beaver winner

2024-08-13T13:09:40Z

DF376:

{{machine|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA}}
The 5-state busy beaver champion (and winner!) is: {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}. It was found by Heiner Marxen and Jürgen Buntrock in 1989<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>. The machine halts after 47,176,870 steps and with 4098 1's on the tape, showing that <math>BB(5) \ge 47{,}176{,}870</math> and <math>\Sigma(5) \ge 4098</math>.

== Behavior ==
This machine repeatedly applies the following map, starting with <math>x = 0</math><ref>Aaronson, S. (2020). The Busy Beaver Frontier. Page 10-11. https://www.scottaaronson.com/papers/bb.pdf</ref>:
<math display="block">\begin{align}
g(x) & \to \frac{5x+18}{3} && \text{if }x \equiv 0 \pmod{3} \\
g(x) & \to \frac{5x+22}{3} && \text{if }x \equiv 1 \pmod{3} \\
g(x) & \to \text{HALT} && \text{if }x \equiv 2 \pmod{3}
\end{align}</math>which can alternatively be written as<ref>Pascal Michel. Behavior of busy beavers.https://bbchallenge.org/~pascal.michel/beh#tm52a</ref>:

<math display="block">\begin{align}
g(3k) & \to 5k+6 \\
g(3k+1) & \to 5k+9 \\
g(3k+2) & \to \text{HALT} \\
\end{align}</math>

The full orbit from <math>x = 0</math> is:
<math display="block">\begin{array}{l}
0 & \to & 6 & \to & 16 & \to & 34 & \to & 64 & \to & \\
114 & \to & 196 & \to & 334 & \to & 564 & \to & 946 & \to & \\
1584 & \to & 2646 & \to & 4416 & \to & 7366 & \to & 12284 & \to & \text{HALT}
\end{array}</math>

== References ==

Skelet 17

2024-08-13T13:08:51Z

DF376:

{{machine|1LB---_0RC1LE_0RD1RC_1LA1RB_0LB0LA}}{{TM|1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA|non-halt}}

Skelet #17 was one of [[Skelet's 43 holdouts]] and one of the last holdouts in BB(5).

The first step towards its resolution was made by savask, who showed the connection to [[wikipedia:Gray_code|Gray Code]]: https://docs.bbchallenge.org/other/skelet17_savasks_analysis.pdf

Building upon this work, Chris Xu produced a full proof of its nonhalting that can be found here: https://chrisxudoesmath.com/papers/skelet17.pdf

Adapting the above, a formal proof of its nonhalting by mxdys can be found here: https://github.com/ccz181078/Coq-BB5/blob/main/Skelet17.md

== TM Behavior ==

{| class="wikitable floatright" style="text-align:center;"
! rowspan="2"|
|-
! 5 !! 4 !! 3 !! 2 !! 1 !! 0 !! value !! length !! <math>\sigma</math>
|-
| 0 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || 0 || 3 || +1
|-
| 1 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|0}} || 1 || 3 || +1
|-
| 1* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#F22"|{{mono|-1}} || 2 || 3 || +1
|-
| 2 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 1 || 2 || -1
|-
| 3 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 3* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 2 || -1
|-
| 4 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|3}} || 0 || 3 || +1
|-
| 5 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || 1 || 3 || +1
|-
| 6 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || 2 || 3 || +1
|-
| 7 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 3 || 3 || +1
|-
| 7* || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 7** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 8 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || 3 || 5 || +1
|-
| 9 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || 4 || 5 || +1
|-
| 10 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|0}} || 5 || 5 || +1
|-
| 10* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#F22"|{{mono|-1}} || 6 || 5 || +1
|-
| 11 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 12 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 13 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 14 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|-
| 14* || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 14** || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 7 || 6 || -1
|-
| 15 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 3 || 5 || +1
|-
| 16 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 4 || 5 || +1
|-
| 17 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 5 || 5 || +1
|-
| 18 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 6 || 5 || +1
|-
| 19 || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|0}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 7 || 5 || +1
|-
| 19* || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#F22"|{{mono|-1}} || 8 || 5 || +1
|-
| 20 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || 4 || 4 || -1
|-
| 21 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || 3 || 4 || -1
|-
| 22 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|1}} || style="background:#DDD"|{{mono|3}} || style="background:#0FF"|{{mono|2}} || 2 || 4 || -1
|-
| 23 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#DDD"|{{mono|3}} || style="background:#DDD"|{{mono|1}} || 1 || 4 || -1
|-
| 24 || style="background:#111"|{{mono|-}} || style="background:#111"|{{mono|-}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|2}} || style="background:#0FF"|{{mono|4}} || style="background:#0FF"|{{mono|0}} || 0 || 4 || -1
|}

It can be shown that when the machine head is at the right end of the tape, the complete tape configuration is of the following form (using [[Directed head notation]]):

<math>0^\infty \; 10^{n_1} \; 1 \; 10^{n_2} \; \dots 1 \; 10^{n_k} \textrm{ B> } \; 0^\infty</math>,

where <math>n_i</math> represents a non-negative integer. Essentially, Skelet 17 builds <math>k</math>-length lists of non-negative numbers delimited with individual cells imprinted with a 1.

The most common transformation (frequency tends to 1 as the number of steps increases) occuring between such configurations is described by Increment rule, similar to the Lucal form of Gray Code: the value at the last index is decremented and the value to the left of the rightmost index with odd value is incremented.

It is useful to consider the following ''state variables'':

* Gray Code value (denoted by <math>n</math>): the integer that is obtained by calculating the parity of each number (except the last) in the list, considering the result as a Gray Code bitstring corresponding to some integer and "recovering" this integer.
* Increment value (denoted by <math>\sigma</math>): the parity of the entire sequence, mapped to <math>\{-1, 1\}</math>. Dirung Increment steps, Skelet 17 counts forwards when <math>\sigma = +1</math> or backwards if <math>\sigma = -1</math>.
* Length of the sequence (including leading zeros).

When started on a blank tape, the machine visits configurations of the form <math>(0, 2, 4, ..., 2^{2k+2}, 0)</math> infinitely often (the step numbers where it occurs approximately equal power of 16: 14, 251, 4088, 65537, 1048646, 16777607, 268437188, etc).

=== Analysis by bisimulation ===

Chris Xu found it useful to divide some tape transformations into two phases, one of them is "virtual" or "invisible", as it does not actually occur on the tape. Indeed, the intermediate step involves negative numbers (the last number being decremented to -1 from 0), which is of course cannot correspond to the <math>10^{a_i}</math> written on the tape.

Such skipped intermediate steps are denoted by asterisk in the table to preserve the "real" step counts (e.g. steps 7* and 7**).

[[Category:Stub]]

Skelet 1

2024-08-13T13:07:42Z

DF376:

{{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC|halt}}{{unsolved|What is the cycle start time of Skelet 1? The best known lower bound is <math>10^{24}</math>.}}{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}
[[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.]]
One of the most challenging [[BB(5)]] Turing machines to prove non-halting. It was eventually proven to be a [[Translated Cycler]] with period 8,468,569,863 and start step over <math>10^{24}</math> (probably much larger!)<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#stats Skelet #1 is infinite] Statistics.</ref>

== References ==
<references />

== See Also ==
* https://www.sligocki.com/2023/02/25/skelet-1-wip.html
* https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html
* https://www.sligocki.com/2023/03/13/skelet-1-infinite.html
[[Category:Stub]]

1RB3RB1LB---2RB 2LA1RA4LB2LA2RA

2024-08-13T13:06:20Z

DF376:

{{machine|1RB3RB1LB---2RB_2LA1RA4LB2LA2RA}}{{TM|1RB3RB1LB---2RB_2LA1RA4LB2LA2RA|undecided}}

This is a [[BB(2,5)]] machine whose behavior is suspected to be similar to [[Skelet 17]].

Analysis shared by Daniel Yuan (@dyuan01) on Discord, [https://discord.com/channels/960643023006490684/1084047886494470185/1251145215461560391 on June 14th 2024]:

I just checked whenever the beaver reaches the 1 on the left side, and calculated the tape for when it next reaches the left side. It would be nice if someone can verify these rules.

<pre>
[x, y, z] := 1 [a+3, b, …]
[2n+1, 2a, 2b, …, 0] -> Halt
[2n+1, 2a, 2b, …, 2m+2] -> [2n, 2a, 2b, …, 2m+2, 0]
[2n+1, 2a, 2b, …, 2m+1] -> [2n, 2a, 2b, …, 2m+1, 1]
[2n+1, 2a, 2b, …, 2m+1, x, …] -> [2n, 2a, 2b, …, 2m+1, x+1, …]
[2n+2, a, b, …] -> [2n+1, a+1, b, …]
</pre>

And you should start at [1, 1].

== Review ==
Matthew House (@LegionMammal978) reviewed the above analysis on [https://discord.com/channels/960643023006490684/1084047886494470185/1251210996224364766 June 14th 2024] and agrees with it.

[[Category:Stub]]

Turing machine

2024-08-13T13:03:55Z

DF376: /* Standard text format */

'''Turing machines''' are a model of computation first introduced by Alan Turing in 1936.<ref>Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". ''Proceedings of the London Mathematical Society''. '''58''': 230–265 https://doi.org/10.1112/plms/s2-42.1.230</ref>
As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors.
In the Busy Beaver space, the following conventions has been adopted:
* The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, <code>0</code> and <code>1</code>, are used, but extended multi-symbol alphabets are also studied.
* The ''configuration'' of the machine at each step of the computation consists of the symbols on the tape, the ''tape head'' pointing at one of the tape positions, and a choice of one of the <math>n</math> states, typically labeled with the first <math>n</math> capital letters of the alphabet.
* The machine starts out in state <code>A</code>, with the tape consisting of a sequence of all zeros.
* At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
** Replace the symbol it has read with a possibly different one;
** Move either left or right;
** Change the state the machine is in.
* Each of the (current state, read symbol) pairs may also correspond to a ''halting transition'', in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional ''halt state'', distinct from any of the <math>n</math> states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by <code>Z</code>.
** It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal <code>1RZ</code> halting transition, or otherwise extended during [[TNF enumeration]].

== Examples ==

The following machine is the longest-running 2-symbol 2-state Turing machine. It terminates after 6 steps.

{| class="wikitable"
|+ BB(2) champion
|-
| || '''0''' || '''1'''
|-
| '''A''' || 1RB || 1LB
|-
| '''B''' || 1LA || 1RZ
|}

The computation proceeds as follows:
<pre>
0. 000 A[0] 000
1. 0001 B[0] 00
2. 000 A[1] 100
3. 00 B[0] 1100
4. 0 A[0] 11100
5. 01 B[1] 1100
6. 011 Z[1] 100
</pre>

== Standard text format ==

To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.<ref> Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html</ref>
The format supports Turing machines with up to 25 states and up to 10 symbols.
As an example, the BB(2) champion listed above would be specified as {{TM|1RB1LB_1LA1RZ|halt}}. A full specification of the format follows.

* Symbols are represented by digits, starting from <code>0</code>
* States are represented by letters, starting from <code>A</code>
* Directions are specified as either <code>L</code> (left) or <code>R</code> (right)
* Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: <code>1RB</code>
* The transitions for a particular state are listed one after another. For example: <code>1RB1LB</code>
* The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
* No unused symbols or states may be present — if state <code>D</code> is in use, states <code>A</code> through <code>C</code> must also be.
* Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of <code>H</code> or <code>Z</code> is encouraged for readability.
* Undefined transitions are represented as <code>---</code>

== See also ==

* [[Directed head notation]]

== References ==
<references />

Template:TM

2024-08-13T13:02:06Z

DF376:

<code>{{#ifexist:{{{1}}}|[[{{{1}}}]]|{{{1}}}|{{{2}}}}}</code> ([https://bbchallenge.org/{{{1}}}&status={{{2}}} bbch])<noinclude>
{{documentation}}
</noinclude>

Cryptids

2024-08-13T11:23:19Z

DF376:

'''Cryptids''' are Turing Machines whose behavior (when started on a blank tape) can be described completely by a relatively simple mathematical rule, but where that rule falls into a class of unsolved (and presumed hard) mathematical problems. This definition is somewhat subjective (What counts as a simple rule? What counts as a hard problem?). In practice, most currently known small Cryptids have [[Collatz-like]] behavior. In other words, the halting problem from blank tape of cryptids is mathematically-hard.

If there exists a Cryptid with n states and m symbols, then BB(n, m) cannot be solved without solving this hard math problem.

The name Cryptid was proposed by Shawn Ligocki in an Oct 2023 [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html blog post] announcing the discovery of [[Bigfoot]].

== Cryptids at the Edge ==

This is a list of Minimal Cryptids (Cryptids in a class with no strictly smaller known Cryptid). All of these Cryptids were "discovered in the wild" rather than "constructed".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
|[[Bigfoot]]
|[[BB(3,3)]]
|{{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}
|[https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is hard]
|Nov 2023
|[[User:Sligocki|Shawn Ligocki]]
|
|-
|[[Hydra]]
|[[BB(2,5)]]
|{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}}
|[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is hard]
|May 2024
|Daniel Yuan
|
|-
|
|BB(2,5)
|{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB|undecided}}
|[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid A Bonus Cryptid]
|May 2024
|Daniel Yuan
|
|-
|[[Antihydra]]
|[[BB(6)]]
|{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
|[https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message]
|June 2024
|<code>@mxdys</code>, shown to be a Cryptid by <code>@racheline</code>.
|Same as '''Hydra''' but starting iteration from 8 instead of 3 and with termination condition <code>O > 2E</code> instead of <code>E > 2O</code>, hence the name '''Antihydra'''.
|}

== Larger Cryptids ==

A more complete list of all known Cryptids over a wider range of states and symbols. These Cryptds were all "constructed" rather than "discovered".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
|RH
|BB(744)
|https://github.com/sorear/metamath-turing-machines/blob/master/riemann-matiyasevich-aaronson.nql
|
|2016
|Matiyasevich and O’Rear
|The machine halts if and only if [https://en.wikipedia.org/wiki/Riemann_hypothesis Riemann Hypothesis] is false.
|-
|Goldbach
|BB(27)
|https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6<nowiki/>(unverified)
|
|2016
|anonymous
|The machine halts if and only if [https://en.wikipedia.org/wiki/Goldbach%27s_conjecture Golbach's conjecture] is false. To the best of our knowledge this construction has not been independently verified.
|-
| Erdős || BB(5,4) and
BB(15)
|
https://docs.bbchallenge.org/other/powers_of_two_5_4.txt

https://docs.bbchallenge.org/other/powers_of_two_15_2.txt
|| [https://arxiv.org/abs/2107.12475 arxiv preprint] || Jul 2021 || [[User:Cosmo|Tristan Stérin]] (<code>@cosmo</code>) and Damien Woods || The machine halts if and only if the following conjecture by Erdős is false: "For all n > 8, there is at least one 2 in the base-3 representation of 2^n"
|-
|Weak Collatz
|BB(124) and BB(43,4)
|https://docs.bbchallenge.org/other/weak_Collatz_conjecture_124_2.txt (unverified)
https://docs.bbchallenge.org/other/weak_Collatz_conjecture_43_4.txt (unverified)
|
|Jul 2021
|[[User:Cosmo|Tristan Stérin]]
|The machine halts if and only if the "weak Collatz conjecture" is false. The weak Collatz conjecture states that the iterated Collatz map (3x+1) has only one cycle on the positive integers.
Not independently verified, and probably easy to further optimise.
|-
| Bigfoot - compiled|| [[BB(7)]]|| <code>0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB</code>|| [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || June 2024 || <code>@Iijil1</code>|| Compilation of Bigfoot into 2 symbols, there was a previous compilation [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-1774200442 with 8 states]
|-
| Hydra - compiled
|BB(9)
|<pre>
0RB0LD_1LC0LI_1LD1LB_0LE0RG_1RF0RH_1RA---_0RD0LB_0RA---_0RF1RZ
</pre>[[File:Hydra_9_states.txt]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1251572501578780782 Discord message]
|June 2024
|<code>@Iijil1</code>
|Compilation of Hydra into 2 symbols, all[https://discord.com/channels/960643023006490684/1084047886494470185/1253193750486974464 confirmed by Shawn Ligocki]. <code>@Iijil1</code> provided 24 TMs which all emulate the same behavior.
[https://discord.com/channels/960643023006490684/1084047886494470185/1247560072427474955 Previous compilation had 10 states], by Daniel Yuan, also [https://discord.com/channels/960643023006490684/1084047886494470185/1247579473042346136 confirmed by Shawn Ligocki].
|}

== Beeping Busy Beaver ==

Cryptids were actually noticed in the [[Beeping Busy Beaver]] problem before they were in the classic Busy Beaver. See [[Mother of Giants]] describing a "family" of Turing machines which "[[probviously]]" [[quasihalt]], but requires solving a Collatz-like problem in order to actually prove it. They are all TMs formed by filling in the missing transition in <code>1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA</code> with different values.

BB(3,3)

2024-08-13T11:21:00Z

DF376: /* Holdouts */

The 3-state, 3-symbol Busy Beaver problem '''BB(3,3)''' is unsolved. With the discovery of [[Bigfoot]] in 2023, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(3,3) and thus [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3,3) is Hard].

The current BB(3,3) champion {{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}} was discovered by Terry and [[User:sligocki|Shawn Ligocki]] in 2007, proving the lower bounds:

<math display="block">\begin{array}{lcrl}
S(3, 3) & \ge & 119{,}112{,}334{,}170{,}342{,}541 & > 10^{17} \\
\Sigma(3, 3) & \ge & 374{,}676{,}383 & > 10^8 \\
\end{array}</math>

On [[bbchallenge.org]] Discord we have reduced the unofficial [[holdouts list]] to 22 TMs. One of these, {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}, is under very active exploration in channel #bb3x3 and believed to be a [[probviously]] halting TM by some members. If it halts, it will be the new champion.

== Cryptids ==
Known BB(3,3) Cryptids:
* {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}, known as [[Bigfoot]]
Possibly probviously halting Cryptid:

* {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}

== Top Halters ==
The current top 10 BB(3,3) halters (known by [[User:sligocki|Shawn Ligocki]]) are
<pre>
0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC Halt 119112334170342541 374676383
1RB2LA1LC_0LA2RB1LB_1RZ1RA1RC Halt 119112334170342540 374676383
1RB2RC1LA_2LA1RB1RZ_2RB2RA1LC Halt 4345166620336565 95524079
1RB1LA2LC_2LA2RB1RB_1RZ0LB0RC Halt 452196003014837 21264944
1RB1RZ2LC_1LC2RB1LB_1LA2RC2LA Halt 4144465135614 2950149
1RB2LA1RA_1RC2RB0RC_1LA1RZ1LA Halt 987522842126 1525688
1RB1RZ2RB_1LC0LB1RA_1RA2LC1RC Halt 4939345068 107900
1RB2LA1RA_1LB1LA2RC_1RZ1LC2RB Halt 1808669066 43925
1RB2LA1RA_1LC1LA2RC_1RZ1LA2RB Halt 1808669046 43925
1RB2LA1RA_1LB1LA2RC_1RZ1LA2RB Halt 1808669046 43925
</pre>
Numbers listed are step count and sigma score for each TM. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm33 '''Historical survey of Busy Beavers'''].

== Holdouts ==
@Justin Blanchard's informal [[Holdouts lists|holdouts list]] is down to 22 TMs as of 9 Jun 2024. @Andrew Ducharme has [https://discord.com/channels/960643023006490684/1259770474897080380/1260476021212188763 categorized] them as follows:

Cryptids
* 829: Bigfoot: {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}

Unsolved:
* Group 1
** {{TM|1RB---0LC_2LC2RC1LB_0RA2RB0LB|undecided}} (21, equivalent to 92 and 818)*
** {{TM|1RB---1RB_2LC2RC1LB_0RA2RB0LB|undecided}} (92, equivalent to 21 and 818)*
** {{TM|1RB2LC---_0LA0RC1LC_1RB2RC1LB|undecided}} (683)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2LA---|undecided}} (816)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2RB2LA|undecided}} (817)*
** {{TM|1RB2RA1LB_0LC0RA1LA_2LA0RB---|undecided}} (818, equivalent to 21 and 92)*
* Group 2
** {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---|undecided}} (153, equivalent to 758)
** {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} (758, equivalent to 153)
* Group 3
** {{TM|1RB2LA1LA_2LA0RA2RC_---0LC2RA|undecided}} (531, equivalent to 532)
** {{TM|1RB2LA1LA_2LA0RA2RC_---1RB2RA|undecided}} (532, equivalent to 531)
* {{TM|1RB1LB2LC_1LA2RB1RB_---0LA2LA|undecided}} (397)
* {{TM|1RB1LC1LC_1LA2RB0RB_2LB---0LA|undecided}} (412)
* {{TM|1RB2LB0LC_2LA2RA1RB_---2LA1LC|undecided}} (650)
<pre>
* = if 816 is non-halting, 21, 92, 683, 817, and 818 are all non-halting.
If 816 halts via transition C2, 817 will halt.
If 816 halts via transition C2, 21, 92, 683 and 818 all halt.
</pre>

TMs with a less rigorous solution/proof:
* {{TM|1RB2LA1LC_1LA2RB1RB_---2LB0LC|undecided}} (543)

TMs that are fully proven by a human or computer, but have not yet received a certificate:
* {{TM|1RB0RC---_2RC0LB1LB_2LC2RA2RB|undecided}} (279)
* {{TM|1RB1LC---_0LC2RB1LB_2LA0RC1RC|undecided}} (400, equivalent to 494)
* {{TM|1RB2LA0LA_2LC---2RA_0RA2RC1LC|undecided}} (494, equivalent to 400)
* {{TM|1RB2LB---_1RC2RB1LC_0LA0RB1LB|undecided}} (642)
* {{TM|1RB2LA2RA_1LC1LB0RA_2RA0LB---|undecided}} (637)
* {{TM|1RB2RB---_1LC2LB1RC_0RA0LB1RB|undecided}} (834)
* {{TM|1RB2RB1LC_1LA2RB0RB_2LB---0LA|undecided}} (867)

BB(3,3)

2024-08-13T11:19:58Z

DF376:

The 3-state, 3-symbol Busy Beaver problem '''BB(3,3)''' is unsolved. With the discovery of [[Bigfoot]] in 2023, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(3,3) and thus [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3,3) is Hard].

The current BB(3,3) champion {{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}} was discovered by Terry and [[User:sligocki|Shawn Ligocki]] in 2007, proving the lower bounds:

<math display="block">\begin{array}{lcrl}
S(3, 3) & \ge & 119{,}112{,}334{,}170{,}342{,}541 & > 10^{17} \\
\Sigma(3, 3) & \ge & 374{,}676{,}383 & > 10^8 \\
\end{array}</math>

On [[bbchallenge.org]] Discord we have reduced the unofficial [[holdouts list]] to 22 TMs. One of these, {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}, is under very active exploration in channel #bb3x3 and believed to be a [[probviously]] halting TM by some members. If it halts, it will be the new champion.

== Cryptids ==
Known BB(3,3) Cryptids:
* {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}, known as [[Bigfoot]]
Possibly probviously halting Cryptid:

* {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}

== Top Halters ==
The current top 10 BB(3,3) halters (known by [[User:sligocki|Shawn Ligocki]]) are
<pre>
0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC Halt 119112334170342541 374676383
1RB2LA1LC_0LA2RB1LB_1RZ1RA1RC Halt 119112334170342540 374676383
1RB2RC1LA_2LA1RB1RZ_2RB2RA1LC Halt 4345166620336565 95524079
1RB1LA2LC_2LA2RB1RB_1RZ0LB0RC Halt 452196003014837 21264944
1RB1RZ2LC_1LC2RB1LB_1LA2RC2LA Halt 4144465135614 2950149
1RB2LA1RA_1RC2RB0RC_1LA1RZ1LA Halt 987522842126 1525688
1RB1RZ2RB_1LC0LB1RA_1RA2LC1RC Halt 4939345068 107900
1RB2LA1RA_1LB1LA2RC_1RZ1LC2RB Halt 1808669066 43925
1RB2LA1RA_1LC1LA2RC_1RZ1LA2RB Halt 1808669046 43925
1RB2LA1RA_1LB1LA2RC_1RZ1LA2RB Halt 1808669046 43925
</pre>
Numbers listed are step count and sigma score for each TM. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm33 '''Historical survey of Busy Beavers'''].

== Holdouts ==
@Justin Blanchard's informal [[Holdouts lists|holdouts list]] is down to 22 TMs as of 9 Jun 2024. @Andrew Ducharme has [https://discord.com/channels/960643023006490684/1259770474897080380/1260476021212188763 categorized] them as follows:

Cryptids
* 829: Bigfoot: {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA}}

Unsolved:
* Group 1
** {{TM|1RB---0LC_2LC2RC1LB_0RA2RB0LB}} (21, equivalent to 92 and 818)*
** {{TM|1RB---1RB_2LC2RC1LB_0RA2RB0LB}} (92, equivalent to 21 and 818)*
** {{TM|1RB2LC---_0LA0RC1LC_1RB2RC1LB}} (683)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2LA---}} (816)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2RB2LA}} (817)*
** {{TM|1RB2RA1LB_0LC0RA1LA_2LA0RB---}} (818, equivalent to 21 and 92)*
* Group 2
** {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}} (153, equivalent to 758)
** {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} (758, equivalent to 153)
* Group 3
** {{TM|1RB2LA1LA_2LA0RA2RC_---0LC2RA}} (531, equivalent to 532)
** {{TM|1RB2LA1LA_2LA0RA2RC_---1RB2RA}} (532, equivalent to 531)
* {{TM|1RB1LB2LC_1LA2RB1RB_---0LA2LA}} (397)
* {{TM|1RB1LC1LC_1LA2RB0RB_2LB---0LA}} (412)
* {{TM|1RB2LB0LC_2LA2RA1RB_---2LA1LC}} (650)
<pre>
* = if 816 is non-halting, 21, 92, 683, 817, and 818 are all non-halting.
If 816 halts via transition C2, 817 will halt.
If 816 halts via transition C2, 21, 92, 683 and 818 all halt.
</pre>

TMs with a less rigorous solution/proof:
* {{TM|1RB2LA1LC_1LA2RB1RB_---2LB0LC}} (543)

TMs that are fully proven by a human or computer, but have not yet received a certificate:
* {{TM|1RB0RC---_2RC0LB1LB_2LC2RA2RB}} (279)
* {{TM|1RB1LC---_0LC2RB1LB_2LA0RC1RC}} (400, equivalent to 494)
* {{TM|1RB2LA0LA_2LC---2RA_0RA2RC1LC}} (494, equivalent to 400)
* {{TM|1RB2LB---_1RC2RB1LC_0LA0RB1LB}} (642)
* {{TM|1RB2LA2RA_1LC1LB0RA_2RA0LB---}} (637)
* {{TM|1RB2RB---_1LC2LB1RC_0RA0LB1RB}} (834)
* {{TM|1RB2RB1LC_1LA2RB0RB_2LB---0LA}} (867)

BB(3,3)

2024-08-13T11:19:31Z

DF376:

The 3-state, 3-symbol Busy Beaver problem '''BB(3,3)''' is unsolved. With the discovery of [[Bigfoot]] in 2023, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(3,3) and thus [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3,3) is Hard].

The current BB(3,3) champion {{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}} was discovered by Terry and [[User:sligocki|Shawn Ligocki]] in 2007, proving the lower bounds:

<math display="block">\begin{array}{lcrl}
S(3, 3) & \ge & 119{,}112{,}334{,}170{,}342{,}541 & > 10^{17} \\
\Sigma(3, 3) & \ge & 374{,}676{,}383 & > 10^8 \\
\end{array}</math>

On [[bbchallenge.org]] Discord we have reduced the unofficial [[holdouts list]] to 22 TMs. One of these, {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}, is under very active exploration in channel #bb3x3 and believed to be a [[probviously]] halting TM by some members. If it halts, it will be the new champion.

== Cryptids ==
Known BB(3,3) Cryptids:
* [[Bigfoot|{{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}]], known as [[Bigfoot]]
Possibly probviously halting Cryptid:

* {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}

== Top Halters ==
The current top 10 BB(3,3) halters (known by [[User:sligocki|Shawn Ligocki]]) are
<pre>
0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC Halt 119112334170342541 374676383
1RB2LA1LC_0LA2RB1LB_1RZ1RA1RC Halt 119112334170342540 374676383
1RB2RC1LA_2LA1RB1RZ_2RB2RA1LC Halt 4345166620336565 95524079
1RB1LA2LC_2LA2RB1RB_1RZ0LB0RC Halt 452196003014837 21264944
1RB1RZ2LC_1LC2RB1LB_1LA2RC2LA Halt 4144465135614 2950149
1RB2LA1RA_1RC2RB0RC_1LA1RZ1LA Halt 987522842126 1525688
1RB1RZ2RB_1LC0LB1RA_1RA2LC1RC Halt 4939345068 107900
1RB2LA1RA_1LB1LA2RC_1RZ1LC2RB Halt 1808669066 43925
1RB2LA1RA_1LC1LA2RC_1RZ1LA2RB Halt 1808669046 43925
1RB2LA1RA_1LB1LA2RC_1RZ1LA2RB Halt 1808669046 43925
</pre>
Numbers listed are step count and sigma score for each TM. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm33 '''Historical survey of Busy Beavers'''].

== Holdouts ==
@Justin Blanchard's informal [[Holdouts lists|holdouts list]] is down to 22 TMs as of 9 Jun 2024. @Andrew Ducharme has [https://discord.com/channels/960643023006490684/1259770474897080380/1260476021212188763 categorized] them as follows:

Cryptids
* 829: Bigfoot: {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA}}

Unsolved:
* Group 1
** {{TM|1RB---0LC_2LC2RC1LB_0RA2RB0LB}} (21, equivalent to 92 and 818)*
** {{TM|1RB---1RB_2LC2RC1LB_0RA2RB0LB}} (92, equivalent to 21 and 818)*
** {{TM|1RB2LC---_0LA0RC1LC_1RB2RC1LB}} (683)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2LA---}} (816)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2RB2LA}} (817)*
** {{TM|1RB2RA1LB_0LC0RA1LA_2LA0RB---}} (818, equivalent to 21 and 92)*
* Group 2
** {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}} (153, equivalent to 758)
** {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} (758, equivalent to 153)
* Group 3
** {{TM|1RB2LA1LA_2LA0RA2RC_---0LC2RA}} (531, equivalent to 532)
** {{TM|1RB2LA1LA_2LA0RA2RC_---1RB2RA}} (532, equivalent to 531)
* {{TM|1RB1LB2LC_1LA2RB1RB_---0LA2LA}} (397)
* {{TM|1RB1LC1LC_1LA2RB0RB_2LB---0LA}} (412)
* {{TM|1RB2LB0LC_2LA2RA1RB_---2LA1LC}} (650)
<pre>
* = if 816 is non-halting, 21, 92, 683, 817, and 818 are all non-halting.
If 816 halts via transition C2, 817 will halt.
If 816 halts via transition C2, 21, 92, 683 and 818 all halt.
</pre>

TMs with a less rigorous solution/proof:
* {{TM|1RB2LA1LC_1LA2RB1RB_---2LB0LC}} (543)

TMs that are fully proven by a human or computer, but have not yet received a certificate:
* {{TM|1RB0RC---_2RC0LB1LB_2LC2RA2RB}} (279)
* {{TM|1RB1LC---_0LC2RB1LB_2LA0RC1RC}} (400, equivalent to 494)
* {{TM|1RB2LA0LA_2LC---2RA_0RA2RC1LC}} (494, equivalent to 400)
* {{TM|1RB2LB---_1RC2RB1LC_0LA0RB1LB}} (642)
* {{TM|1RB2LA2RA_1LC1LB0RA_2RA0LB---}} (637)
* {{TM|1RB2RB---_1LC2LB1RC_0RA0LB1RB}} (834)
* {{TM|1RB2RB1LC_1LA2RB0RB_2LB---0LA}} (867)

BB(3,3)

2024-08-13T11:17:35Z

DF376:

The 3-state, 3-symbol Busy Beaver problem '''BB(3,3)''' is unsolved. With the discovery of [[Bigfoot]] in 2023, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(3,3) and thus [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3,3) is Hard].

The current BB(3,3) champion {{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}} was discovered by Terry and [[User:sligocki|Shawn Ligocki]] in 2007, proving the lower bounds:

<math display="block">\begin{array}{lcrl}
S(3, 3) & \ge & 119{,}112{,}334{,}170{,}342{,}541 & > 10^{17} \\
\Sigma(3, 3) & \ge & 374{,}676{,}383 & > 10^8 \\
\end{array}</math>

On [[bbchallenge.org]] Discord we have reduced the unofficial [[holdouts list]] to 22 TMs. One of these, {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}, is under very active exploration in channel #bb3x3 and believed to be a [[probviously]] halting TM by some members. If it halts, it will be the new champion.

== Cryptids ==
Known BB(3,3) Cryptids:
* [[Bigfoot]]
Possibly probviously halting Cryptid:

* {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA}}

== Top Halters ==
The current top 10 BB(3,3) halters (known by [[User:sligocki|Shawn Ligocki]]) are
<pre>
0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC Halt 119112334170342541 374676383
1RB2LA1LC_0LA2RB1LB_1RZ1RA1RC Halt 119112334170342540 374676383
1RB2RC1LA_2LA1RB1RZ_2RB2RA1LC Halt 4345166620336565 95524079
1RB1LA2LC_2LA2RB1RB_1RZ0LB0RC Halt 452196003014837 21264944
1RB1RZ2LC_1LC2RB1LB_1LA2RC2LA Halt 4144465135614 2950149
1RB2LA1RA_1RC2RB0RC_1LA1RZ1LA Halt 987522842126 1525688
1RB1RZ2RB_1LC0LB1RA_1RA2LC1RC Halt 4939345068 107900
1RB2LA1RA_1LB1LA2RC_1RZ1LC2RB Halt 1808669066 43925
1RB2LA1RA_1LC1LA2RC_1RZ1LA2RB Halt 1808669046 43925
1RB2LA1RA_1LB1LA2RC_1RZ1LA2RB Halt 1808669046 43925
</pre>
Numbers listed are step count and sigma score for each TM. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x3. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm33 '''Historical survey of Busy Beavers'''].

== Holdouts ==
@Justin Blanchard's informal [[Holdouts lists|holdouts list]] is down to 22 TMs as of 9 Jun 2024. @Andrew Ducharme has [https://discord.com/channels/960643023006490684/1259770474897080380/1260476021212188763 categorized] them as follows:

Cryptids
* 829: Bigfoot: {{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA}}

Unsolved:
* Group 1
** {{TM|1RB---0LC_2LC2RC1LB_0RA2RB0LB}} (21, equivalent to 92 and 818)*
** {{TM|1RB---1RB_2LC2RC1LB_0RA2RB0LB}} (92, equivalent to 21 and 818)*
** {{TM|1RB2LC---_0LA0RC1LC_1RB2RC1LB}} (683)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2LA---}} (816)*
** {{TM|1RB2RA1LB_0LC0RA1LA_---2RB2LA}} (817)*
** {{TM|1RB2RA1LB_0LC0RA1LA_2LA0RB---}} (818, equivalent to 21 and 92)*
* Group 2
** {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}} (153, equivalent to 758)
** {{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} (758, equivalent to 153)
* Group 3
** {{TM|1RB2LA1LA_2LA0RA2RC_---0LC2RA}} (531, equivalent to 532)
** {{TM|1RB2LA1LA_2LA0RA2RC_---1RB2RA}} (532, equivalent to 531)
* {{TM|1RB1LB2LC_1LA2RB1RB_---0LA2LA}} (397)
* {{TM|1RB1LC1LC_1LA2RB0RB_2LB---0LA}} (412)
* {{TM|1RB2LB0LC_2LA2RA1RB_---2LA1LC}} (650)
<pre>
* = if 816 is non-halting, 21, 92, 683, 817, and 818 are all non-halting.
If 816 halts via transition C2, 817 will halt.
If 816 halts via transition C2, 21, 92, 683 and 818 all halt.
</pre>

TMs with a less rigorous solution/proof:
* {{TM|1RB2LA1LC_1LA2RB1RB_---2LB0LC}} (543)

TMs that are fully proven by a human or computer, but have not yet received a certificate:
* {{TM|1RB0RC---_2RC0LB1LB_2LC2RA2RB}} (279)
* {{TM|1RB1LC---_0LC2RB1LB_2LA0RC1RC}} (400, equivalent to 494)
* {{TM|1RB2LA0LA_2LC---2RA_0RA2RC1LC}} (494, equivalent to 400)
* {{TM|1RB2LB---_1RC2RB1LC_0LA0RB1LB}} (642)
* {{TM|1RB2LA2RA_1LC1LB0RA_2RA0LB---}} (637)
* {{TM|1RB2RB---_1LC2LB1RC_0RA0LB1RB}} (834)
* {{TM|1RB2RB1LC_1LA2RB0RB_2LB---0LA}} (867)

BB(6)

2024-08-13T11:14:08Z

DF376:

The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).

The current BB(6) champion {{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}} was discovered by Pavel Kropitz in 2022 proving the lower bound:<ref>Shawn Ligocki. 2022. "BB(6, 2) > 10↑↑15". https://www.sligocki.com/2022/06/21/bb-6-2-t15.html</ref>

<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>

== Techniques ==
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:

<math display="block">\begin{array}{l}
C(4k) & \to & Halt(\frac{3^{k+3} - 11}{2}) \\
C(4k+1) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+2) & \to & C(\frac{3^{k+3} - 11}{2}) \\
C(4k+3) & \to & C(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to [[wikipedia:Euler's_totient_function|Euler's_totient_function]]).

== Cryptids ==
Known BB(6) Cryptids:

* [[Antihydra]]
* {{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}} a variant of [[Hydra]] and [[Antihydra]]
* {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}} (and 15 related TMs) a family of [[probviously]] halting cryptids

Potential Cryptids:

* {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
* {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}

== Top Halters ==
The current top 10 BB(6) halters (known by [[User:Sligocki|Shawn Ligocki]]) are<pre>
1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE Halt ~10↑↑15.60465
1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD Halt ~10↑↑5.63534
1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC Halt ~10↑↑5.56344
1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ Halt ~10↑↑5.12468
1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ Halt ~10↑↑5.03230
1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA Halt ~10↑↑4.91072
1RB0LE_1LC1RA_1RE0LD_1LC1LF_1LA0RC_1RZ1LC Halt ~10↑↑3.33186
1RB1RF_1LC1RE_0LD1LB_1LA0RA_0RA0RB_1RZ0RD Halt ~10↑↑3.31128
1RB0LF_1LC0RA_1RD0LB_1LE1RC_1RZ1LA_1LA1LE Halt ~10↑↑3.18855
1RB1RZ_0LC0LD_1LD1LC_1RE1LB_1RF1RD_0LD0RA Halt ~10^646456993.24591
</pre>The numbers listed are sigma scores. Runtimes are not available, but are presumed to be about <math>score^2</math> which is roughly indistinguishable in tetration notation. Fractional tetration notation is described in https://www.sligocki.com/2022/06/25/ext-up-notation.html. For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm62 '''Historical survey of Busy Beavers'''].

== Holdouts ==
@mxdys's informal [[Holdouts lists|holdouts list]] is down to 5877 TMs as of 4 Aug 2024.

== References ==
<references />

BB(5)

2024-08-13T11:11:44Z

DF376: /* Champions */

'''BB(5)''' refers to the 5th value of the [[Busy Beaver function]]. In 1989, the [[5-state busy beaver winner]] was found: a 5-state [[Turing machine]] halting after 47,176,870 giving the lower bound BB(5) ≥ 47,176,870.<ref name=":0">H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>

In 2024, BB(5) = 47,176,870 was proven by the [[bbchallenge.org]] massively collaborative research project.

== History ==
In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations, see [[Busy Beaver Functions]].

=== Finding the 5-state winner ===

* In 1964, Green establishes Σ(5) ≥ 17.<ref name=":1">Pascal Michel. (2022). The Busy Beaver Competition: a historical survey. https://bbchallenge.org/~pascal.michel/ha#tm52 </ref>
* In 1972, Lynn establishes S(5) ≥ 435 and Σ(5) ≥ 22.<ref name=":1" />
* In 1973, Weimann establishes S(5) ≥ 556 and Σ(5) ≥ 40.<ref name=":1" />
* In 1974, Lynn, cited by Brady (1983)<ref>Brady, A.H. (1983). The determination of the value of Rado’s noncomputable function Σ() for four-state Turing machines. ''Mathematics of Computation, 40'', 647-665.</ref>, establishes S(5) ≥ 7,707 and Σ(5) ≥ 112.
* In 1983, the [https://docs.bbchallenge.org/other/lud20.pdf Dortmund contest]is organised to find new 5-state champions, winner is Uwe Schult who established S(5) ≥ 134,467 and Σ(5) ≥ 501.
* In 1984, George Uhing establishes S(5) ≥ 2,133,492 and Σ(5) ≥ 1,915.<ref>https://docs.bbchallenge.org/other/busy.html</ref>
* In 1989, Heiner and Buntrock find the [[5-state busy beaver winner]], establishing S(5) ≥ 47,176,870 and Σ(5) ≥ 4,098.<ref name=":0" /> They do not prove (or claim) that the machine is the actual winner (i.e. that no other 5-state machines halt after more steps) but they present some ideas for automatically deciding the behavior of Turing machines (i.e. making [[Deciders]]).<ref name=":0" />

=== Proving that the 5-state winner is actually the winner ===
No machine halting in more steps than the [[5-state busy beaver winner]] has been found since 1989, hinting that it is actually the 5-state winner (i.e. no 5-state machine could halt after more steps). In 2020, Scott Aaronson formally conjectured that BB(5) = 47,176,870.<ref>Scott Aaronson. 2020. The Busy Beaver Frontier. SIGACT News 51, 3 (August 2020), 32–54. <nowiki>https://doi.org/10.1145/3427361.3427369</nowiki></ref> In practice, proving this conjecture requires to study the behavior of ~100 million 5-state machines.<ref>https://bbchallenge.org/method</ref>
* In 2003, Georgi Georgiev (Skelet) publishes a list of [[Skelet's 43 holdouts|43 holdouts]], based on [[bbfind]], a collection of [[Deciders]] written in Pascal.<ref>https://skelet.ludost.net/bb/index.html</ref>
* In 2009, Joachim Hertel publishes a method claiming 100 holdouts.<ref>Function, S., & Hertel, J. (2009). Computing the Uncomputable Rado Sigma Function. https://www.mathematica-journal.com/2009/11/23/computing-the-uncomputable-rado-sigma-function/</ref>
* In 2022, [[bbchallenge.org]] is released, with the aim of collaboratively proving that BB(5) = 47,176,870.<ref>https://bbchallenge.org/story</ref>
* In 2024, bbchallenge's contributor @mxdys publishes [[Coq-BB5]], a Coq-verified proof of BB(5) = 47,176,870<ref>https://github.com/ccz181078/Coq-BB5</ref>, ending a 60 years old quest. This proof uses and/or improves on many other bbchallenge's contributions, see [[Coq-BB5]].

== Champions ==
S(5) = 47,176,870 and there is only one shift champion (in [[TNF]]):

* {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}} leaves 4098 ones (a ones champion)

Σ(5) = 4098 and there are 2 ones champions (in TNF):

* {{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}} runs for 47,176,870 steps (the steps champion)
* {{TM|1RB1RA_1LC1LB_1RA1LD_1RA1LE_1RZ0LC|halt}} runs for 11,798,826 steps

== Enumeration ==
The top longest running BB(5) TMs (in [[TNF-1RB]]) are:
<pre>
Standard format Status S Σ
1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA Halt 47176870 4098
1RB0LD_1LC1RD_1LA1LC_1RZ1RE_1RA0RB Halt 23554764 4097
1RB1RA_1LC1LB_1RA0LD_0RB1LE_1RZ0RB Halt 11821234 4097
1RB1RA_1LC1LB_1RA0LD_1RC1LE_1RZ0RB Halt 11821220 4097
1RB1RA_0LC0RC_1RZ1RD_1LE0LA_1LA1LE Halt 11821190 4096
1RB1RA_1LC0RD_1LA1LC_1RZ1RE_1LC0LA Halt 11815076 4096
1RB1RA_1LC1LB_1RA0LD_0RB1LE_1RZ1LC Halt 11811040 4097
1RB1RA_1LC1LB_0RC1LD_1RA0LE_1RZ1LC Halt 11811040 4097
1RB1RA_1LC1LB_1RA0LD_1RC1LE_1RZ1LC Halt 11811026 4097
1RB1RA_0LC0RC_1RZ1RD_1LE1RB_1LA1LE Halt 11811010 4096
1RB1RA_1LC1LB_1RA1LD_0RE0LE_1RZ1LC Halt 11804940 4097
1RB1RA_1LC1LB_1RA1LD_1RA0LE_1RZ1LC Halt 11804926 4097
1RB1RA_1LC0RD_1LA1LC_1RZ1RE_0LE1RB Halt 11804910 4096
1RB1RA_1LC0RD_1LA1LC_1RZ1RE_1LC1RB Halt 11804896 4096
1RB1RA_1LC1LB_1RA1LD_1RA1LE_1RZ0LC Halt 11798826 4098
1RB1RA_1LC1RD_1LA1LC_1RZ0RE_1LC1RB Halt 11798796 4097
1RB1RA_1LC1RD_1LA1LC_1RZ1RE_0LE0RB Halt 11792724 4097
1RB1RA_1LC1RD_1LA1LC_1RZ1RE_1LA0RB Halt 11792696 4097
1RB1RA_1LC1RD_1LA1LC_1RZ1RE_1RA0RB Halt 11792682 4097
1RB1RZ_1LC1RC_0RE0LD_1LC0LB_1RD1RA Halt 2358064 1471
</pre>
For more top halting BB(5) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/5x2

== References ==

BB(4)

2024-08-13T11:11:11Z

DF376:

'''BB(4)''' refers to the 4th value of the [[Busy Beaver function]].

== History ==
In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].

* In 1965, Allen Brady proves that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
* In 1966, Allen Brady conjectures Σ(4) = 13 and S(4) = 107 (He says S(4) = 106, but this seems to be based upon a slightly different version of S function).<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
* In 1974, Allen Brady proves that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
* In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref> Some holdouts were not rigorously handled by the proof: ''"All of the remaining holdouts were examined by means of voluminous printouts of their histories along with some program extracted features. It was determined to the author's satisfaction that none of these machines will ever stop."''<ref name=":0" />
* In 2024, S(4) = 107 was confirmed as part of [[Coq-BB5]]. <ref>https://github.com/ccz181078/Coq-BB5/blob/main/BB42Theorem.v</ref>

== Champions ==
S(4) = 107 and there is only one shift champion (in [[TNF]]):

* {{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}} leaves 13 ones (a ones champion)

Σ(4) = 13 and there are 2 ones champions (in TNF):

* {{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}} runs 107 steps (the steps champion)

* {{TM|1RB0RC_1LA1RA_1RZ1RD_1LD0LB|halt}} runs 96 steps

== Enumeration ==
In [[TNF-1RB]] there are exactly 620,261 BB(4) TMs of which 183,983 halt. The top longest running TMs are:<pre>
1RB1LB_1LA0LC_1RZ1LD_1RD0RA Halt 107 13
1RB1LD_1LC0RB_1RA1LA_1RZ0LC Halt 97 9
1RB0RC_1LA1RA_1RZ1RD_1LD0LB Halt 96 13
1RB1LB_0LC0RD_1RZ1LA_1RA0LA Halt 96 6
1RB1LD_0LC0RC_1LC1LA_1RZ0LA Halt 84 11
1RB1RZ_1LC0RD_1LA1LB_0LC1RD Halt 83 8
1RB0RD_1LC0LA_1RA1LB_1RZ0RC Halt 78 12
1RB1LA_0RC0RD_1LC0LA_1RZ0RC Halt 78 9
1RB0RD_0RC0RA_1LC0LA_0RB1RZ Halt 75 9
1RB0RC_1LC1RA_1RZ0LD_1RA1LA Halt 74 8
1RB1LA_0LA1RC_1RA0RD_1RZ0RB Halt 70 8
1RB1LC_0RC0RB_0LD0LA_1LA1RZ Halt 69 7
1RB1LA_1LA1RC_1RZ0RD_0LD1RB Halt 69 7
1RB1RZ_1LC1RA_0RC0LD_1RD0LB Halt 68 10
1RB0LB_0RC0RD_1LD1LA_0LA1RZ Halt 68 8
1RB1LB_0RC1RZ_1LC1LD_0RD0LA Halt 68 7
1RB0RD_0RC1RZ_1LC0LA_0RA0RB Halt 68 7
1RB0LD_0RC1LD_1LC0RB_0LA1RZ Halt 67 7
1RB1LA_1RC0LD_0LA0RC_1RZ1LB Halt 66 7
1RB1RC_1LC1RD_1RZ0LD_1LA0RA Halt 65 7
</pre>For the top 1000 halting BB(4) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/4x2.txt

== References ==

BB(3)

2024-08-13T11:10:36Z

DF376: Updated the templates

The 3-state 2-symbol Busy Beaver problem '''BB(3)''' was proven by Shen Lin in his 1963 doctoral dissertation<ref>Shen Lin. 1963. Computer studies of Turing machine problems. PhD dissertation. Ohio State University. https://etd.ohiolink.edu/acprod/odb_etd/etd/r/1501/10?clear=10&p10_accession_num=osu1486554418657614</ref> and republished in 1965.<ref>Lin, Shen; Radó, Tibor (April 1965). "Computer Studies of Turing Machine Problems". ''Journal of the ACM''. '''12''' (2): 196–212. https://doi.org/10.1145/321264.321270</ref> Allen Brady independently proved it in his 1964 PhD dissertation.<ref>Allen Brady. 1964. Solutions of Restricted Cases of the Halting Problem Applied to the Determination of Particular Values of a Non-Computable Function. PhD dissertation. Oregon State University. https://ir.library.oregonstate.edu/downloads/6q182n74x</ref>

== Techniques ==
In order to prove BB(3), Lin discovered [[Translated Cycler]]s (which he called "partial recurrence") and described the first algorithm for proving them infinite.

== Champions ==
S(3) = 21 and there is only one shift champion (in [[TNF]]):

* {{TM|1RB1RZ_1LB0RC_1LC1LA|halt}} leaves 5 ones

Σ(3) = 6 and there are 5 ones champions (in TNF):

* {{TM|1RB1RZ_0RC1RB_1LC1LA|halt}} runs for 14 steps
* {{TM|1RB1RC_1LC1RZ_1RA0LB|halt}} runs for 13 steps
* {{TM|1RB1LC_1LA1RB_1LB1RZ|halt}} runs for 13 steps
* {{TM|1RB1RA_1LC1RZ_1RA1LB|halt}} runs for 12 steps
* {{TM|1RB1LC_1RC1RZ_1LA0LB|halt}} runs for 11 steps
BB(3) is notable for being the only known size where none of the shift champions are also ones champions.

== Enumeration ==
In [[TNF-1RB]] there are exactly 4057 BB(3) TMs of which 1379 halt. The top longest running TMs are:<pre>
1RB1RZ_1LB0RC_1LC1LA Halt 21 5
1RB1RZ_0LC0RC_1LC1LA Halt 20 5
1RB1LA_0RC1RZ_1LC0LA Halt 20 5
1RB1RA_0RC1RZ_1LC0LA Halt 19 5
1RB0RA_0RC1RZ_1LC0LA Halt 19 4
1RB0LC_1LA1RZ_1RC1RB Halt 18 5
1RB0LB_0RC1RC_1LA1RZ Halt 18 5
1RB1LB_0RC1RZ_1LC0LA Halt 18 4
1RB0LB_0RC1RZ_1LC0LA Halt 18 3
1RB1RZ_0RC0RC_1LC1LA Halt 17 5
1RB1RZ_0RC---_1LC0LA Halt 17 4
1RB1LC_0LC1RA_1RZ1LA Halt 16 5
1RB0LC_1LC1RB_1RZ1LA Halt 16 5
1RB1LA_0LA1RC_1RA1RZ Halt 15 5
1RB1LA_0LA1RC_0RB1RZ Halt 15 4
1RB0LC_1RC1RZ_1LA0RB Halt 15 4
1RB0RB_0LC1RZ_1RA1LC Halt 15 3
1RB1RZ_0RC1RB_1LC1LA Halt 14 6
1RB1RZ_1LB0LC_1RA1RC Halt 14 5
1RB1RZ_0LC1RA_1LA1LB Halt 14 5
1RB1RZ_1LC1RA_1RC0LB Halt 14 4
1RB1RZ_1LB0LC_1RA0RC Halt 14 3
1RB1RZ_0LC0RB_1LA1LC Halt 14 3
1RB0RB_1LC1RZ_0LA1RA Halt 14 3
1RB1RZ_0LC0RA_1RA1LB Halt 14 2
</pre>For a full list of halting BB(3) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/3x2.txt

== References ==
<references />

BB(2)

2024-08-13T11:08:43Z

DF376: Updated the Template

The 2-state 2-symbol Busy Beaver problem '''BB(2)''' was solved by Tibor Radó using pencil and paper and announced in his seminal Busy Beaver paper, On Non-Computable Functions.<ref>Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. <nowiki>https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</nowiki></ref>

== Champions ==
S(2) = 6 and there are 5 shift champions in [[TNF]]:

* {{TM|1RB1LB_1LA1RZ|halt}} leaves 4 ones (the ones champion)
* {{TM|1RB0LB_1LA1RZ|halt}} leaves 3 ones
* {{TM|1RB1RZ_1LB1LA|halt}} leaves 3 ones
* {{TM|1RB1RZ_0LB1LA|halt}} leaves 2 ones
* {{TM|0RB1RZ_1LA1RB|halt}} leaves 2 ones

Σ(2) = 4 and there is one unique ones champion in TNF:

* {{TM|1RB1LB_1LA1RZ|halt}} runs for 6 steps (a shift champion)

== Enumeration ==
In [[TNF-1RB]] there are exactly 41 BB(2) TMs of which 15 halt:

<pre>
1RB1LB_1LA1RZ Halt 6 4
1RB1RZ_1LB1LA Halt 6 3
1RB0LB_1LA1RZ Halt 6 3
1RB1RZ_0LB1LA Halt 6 2
1RB1LA_1LA1RZ Halt 5 3
1RB1LA_0LA1RZ Halt 5 2
1RB1RZ_1LB1RA Halt 4 2
1RB1RB_1LA1RZ Halt 4 2
1RB1RZ_1LB0RA Halt 4 1
1RB0RB_1LA1RZ Halt 4 1
1RB1RZ_1LA--- Halt 3 2
1RB---_1LB1RZ Halt 3 2
1RB1RZ_0LA--- Halt 3 1
1RB---_0LB1RZ Halt 3 1
1RB---_1RZ--- Halt 2 2
</pre>

and 26 are infinite:

<pre>
1RB1RB_0LA---
1RB1RA_1LA---
1RB1RA_0LA---
1RB1LB_0LA---
1RB0RB_0LA---
1RB0RA_1LA---
1RB0RA_0LA---
1RB0LB_0LA---
1RB0LA_1LA---
1RB0LA_0LA---
1RB---_1RB---
1RB---_1RA---
1RB---_1LB1RB
1RB---_1LB1LB
1RB---_1LB0RB
1RB---_1LB0LB
1RB---_1LB0LA
1RB---_0RB---
1RB---_0RA---
1RB---_0LB1RB
1RB---_0LB1RA
1RB---_0LB1LB
1RB---_0LB0RB
1RB---_0LB0RA
1RB---_0LB0LB
1RB---_0LB0LA
</pre>

== References ==
<references />

Template:TM

2024-08-13T11:05:08Z

DF376:

<code>{{#ifexist:{{{1}}}|[[{{{1}}}]]|{{{1}}}}|{{{2}}}}}</code> ([https://bbchallenge.org/{{{1}}}&status={{{2}}} bbch])<noinclude>
{{documentation}}
</noinclude>

Template:TM

2024-08-13T11:04:21Z

DF376: Undo revision 646 by DF376 (talk)

<code>{{#ifexist:{{{1}}}|[[{{{1}}}]]|{{{1}}}}}</code> ([https://bbchallenge.org/{{{1}}} bbch])<noinclude>
{{documentation}}
</noinclude>

Template:TM

2024-08-13T11:03:43Z

DF376:

<code>{{#ifexist:{{{TMName}}}|[[{{{TMName}}}]]|{{{TMName}}}}}</code> ([https://bbchallenge.org/{{{TMName}}} bbch])<noinclude>
{{documentation}}
</noinclude>