User:Azerty/Busy Beaver Functions: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Azerty (talk | contribs)
142 edits
Azerty (talk | contribs)
142 edits
 
(30 intermediate revisions by the same user not shown)
Line 1: Line 1:
This is a list of Busy Beaver functions for Turing machines and other simple Turing-complete systems and their current lower bounds.
This is a list of Busy Beaver functions for Turing machines and other simple Turing-complete systems and their current lower bounds.


All functions here grow uncomputably fast like the original Busy Beaver function. There is no function that grow much faster like the Beeping Busy Beaver function here.
I only add functions that follow the requirements below:
 
* The function must grow uncomputably fast, like BB(n).
* The function must not grow uncomputably faster than BB(n), like BBB(n).
* The function must not have similar champions to other function, like Σ(n).
* The function must not be unecessary complex.


== Turing machines ==
== Turing machines ==


=== Normal ===
=== [[Busy Beaver Functions|Classic]] ===
Maximum number of steps done by a n-state, m-symbol Turing Machine with k+1 undefined transitions before halting. TMs halt when they are on an undefined transititon.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 54: Line 60:
|139
|139
|{{TM|1RB1LB_1LA0LC_---1LD_1RE1LE_---0RA|halt}}
|{{TM|1RB1LB_1LA0LC_---1LD_1RE1LE_---0RA|halt}}
|-
|BB(3,3,1)
|678
|{{TM|1RB1LB1LA_2RC2RB---_0LA1RC---|halt}}
|-
|-
|[[BB(2,4)]]
|[[BB(2,4)]]
|3,932,964
|3,932,964
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---|halt}}
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---|halt}}
|-
|BB(3,3,1)
|3,932,964
|{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---|halt}}
|-
|-
|[[BB(5)|BB(5,2)]]
|[[BB(5)|BB(5,2)]]
|47,176,870
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA|halt}}
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA|halt}}
|-
|BB(6,2,1)
|17,397,627,083
|{{TM|1RB0LA_1RC1RD_1LB1RA_---0RE_1LF0RC_1LA---|halt}}
|-
|-
|[[BB(3,3)]]
|[[BB(3,3)]]
Line 132: Line 142:
|}
|}


=== Blanking ===
=== [[Blanking Busy Beaver Function|Blanking]] ===
Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 171: Line 182:
|}
|}


=== Reversible ===
=== [[Reversible Turing Machine|Reversible]] ===
Maximum number of steps done by a n-state, m-symbol reversible Turing Machine with k+1 undefined transitions before halting.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 206: Line 218:
|}
|}


=== Consecutive ones ===
=== [[Maximum Consecutive Ones Function|Consecutive ones]] ===
Maximum number of consecutive 1s left on the tape by a n-state, m-symbol Turing Machine with k+1 undefined transitions after halting. TMs must leave all their 1s consecutively.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 241: Line 254:
|}
|}


=== Semi infinite tape ===
=== Semi-infinite tape ===
Maximum number of right steps done by a n-state, m-symbol Turing Machine with k undefined transitions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 248: Line 262:
|-
|-
|BBt(2,2,1)
|BBt(2,2,1)
|1
|3
|{{TM|1RB1LA_1LA---|halt}}
|{{TM|1RB---_1LB0RB|halt}}
|-
|-
|BBt(2,2)
|BBt(2,2)
|2
|3
|{{TM|1RB1RB_1LA1LB|halt}}
|{{TM|1RB---_1LB0RB|halt}}
|-
|BBt(2,3,1)
|9
|{{TM|1RB---2RB_2LB2RA0RB|halt}}
|-
|-
|BBt(3,2,1)
|BBt(3,2,1)
|4
|11
|{{TM|0RB---_1LA1RC_1LB0LC|halt}}
|{{TM|1RB---_0RC0RB_1LB1LC|halt}}
|-
|-
|BBt(3,2)
|BBt(3,2)
|6
|12
|{{TM|0RB1RC_1LA1RB_1RB0LC|halt}}
|{{TM|0RB0LB_0RC1RC_1LA0LC|halt}}
|-
|BBt(2,3)
|17
|{{TM|1RB0RA0RB_2LA2RB1LB|halt}}
|-
|BBt(2,4,1)
|22
|{{TM|3RB2LB1RB1RA_2LA2RB1LA---|halt}}
|-
|BBt(4,2,1)
|26
|{{TM|1RB---_1RC0LD_0RD0RC_1LC1LD|halt}}
|-
|BBt(2,4)
|33
|{{TM|3RB2LB1RA2RB_3LB2RA1LA0RA|halt}}
|-
|BBt(4,2)
|60
|{{TM|1RB1RC_0RD0RC_1RD1LD_1LA0LB|halt}}
|-
|BBt(3,3,2)
|70
|{{TM|1RB---2RB_2RC---1RC_2LC2RA0RC|halt}}
|-
|BBt(3,3,1)
|70
|{{TM|1RB---2RB_2RC---1RC_2LC2RA0RC|halt}}
|-
|BBt(3,3)
|156
|{{TM|2RB0LA1RC_1LA2LB1RB_2LC0RC0RB|halt}}
|}
|}


=== Preperiodic ===
=== [[Non-halting Turing machine#Translated cycler preperiod|Preperiodic]] ===
Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions before turning into a translated cycler.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
!Lower Bound
!Lower Bound
!Champion
!
|-
|BBS(2,2,1)
|4
|{{TM|1RB---_1LB0RB}}
|-
|-
|BBS(2,2)
|BBS(2,2)
Line 283: Line 338:
|-
|-
|BBS(2,4)
|BBS(2,4)
|293,225,660,896
|<math>2 \times 10^{23}</math>
|{{TM|1RB2LA0RA3LA_1LA1LB3RB1RA}}
|{{TM|1RB2LA1RA1LB_0LB2RB3RB1LA}}
|-
|BBP(5,2,1)
|<math>5.418 \times 10^{51}</math>
|{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}
|-
|BBP(5,2)
|<math>10^{14,006}</math>
|{{TM|1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA}}
|-
|BBP(3,3)
|<math>10 {\uparrow}^{2} 6</math>
|{{TM|1RB0LB2LA_1LA0RC0LB_2RC2RB0LC}}
|}
|}


=== Periodic (to do) ===
=== [[Non-halting Turing machine#Translated cycler period|Periodic]] ===
Maximum translated cycler period done by a n-state, m-symbol Turing Machine with k undefined transitions.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 293: Line 361:
!Champion
!Champion
|-
|-
|
|BBP(2,2,1)
|
|3
|
|{{TM|1RB---_0LB1RA}}
|-
|BBP(2,2)
|9
|{{TM|1RB0RB_1LB1RA}}
|-
|BBP(3,2)
|92
|{{TM|1RB0LA_0RC1LA_1LC0RB}}
|-
|BBP(3,3)
|336
|{{TM|2RB0LA1RC_1LA2LB1RB_2LC0RC0RB}}
|-
|BBP(2,4)
|33,209,131
|{{TM|1RB0RA3LB1RB_2LA0LB1RA2RB}}
|-
|BBP(4,2)
|212,081,736
|{{TM|1RB0LA_0RC1RD_1LD0RB_1LA1RB}}
|-
|-
|
|BBP(5,2,1)
|
|8,468,569,863
|
|{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}
|}
|}


=== Turmite ===
=== [[Terminating Turmite|Turmite]] ===
Maximum number of steps done by a n-state, m-symbol Turmite Machine with k+1 undefined transitions before halting.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 309: Line 398:
|-
|-
|TT(2,2,1)
|TT(2,2,1)
|3
|6
|<code>1PB---_1TA---</code>
|<code>0PB---_1TA---</code>
|-
|-
|TT(2,2)
|TT(2,2)
|6
|13
|<code>1PB1PB_1TA---</code>
|<code>1TB---_1PA0PB</code>
|-
|TT(2,3,1)
|20
|<code>1TB------_1PA2PB0PB</code>
|-
|TT(3,2,1)
|20
|<code>1TB---_1PC0PB_1PA---</code>
|-
|TT(3,2)
|82
|<code>1PB0PA_1TA0PC_1PA---</code>
|-
|TT(4,2,1)
|95
|<code>1TB1PB_1PC---_0PA0TD_---0TB</code>
|-
|TT(2,3)
|223
|<code>1TB0PA2PA_2PA---1PA</code>
|-
|TT(4,2)
|758
|<code>1TB---_0PD1PB_1PA1TA_0PC0PD</code>
|-
|TT(2,4)
|1,068
|<code>1TB3TB2PB---_2TB1PA0PA2TB</code>
|}
|}


Line 383: Line 500:
!Champion
!Champion
|-
|-
|BBL(6)
|BBL(7)
|6
|7
|<code>\1 1 1 1 1 1</code>
|<code>\1 1 1 1 1 1</code>
|-
|-
|BBL(7)
|BBL(8)
|15
|16
|<code>(\1 1) (\\2 (1 2))</code>
|<code>(\1 1) (\\2 (1 2))</code>
|-
|-
|BBL(8)
|BBL(9)
|67
|68
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|-
|-
|BBL(9)
|BBL(10)
|<math>7.625 \times 10^{12}</math>
|<math>7.625 \times 10^{12}</math>
|<code>(\1 1 1) (\\2 (2 (2 1)))</code>
|<code>(\1 1 1) (\\2 (2 (2 1)))</code>
|-
|-
|BBL(10)
|BBL(11)
|<math>10^{7.625 \times 10^{12}}</math>
|<math>10^{7.625 \times 10^{12}}</math>
|<code>(\1 1 1 1) (\\2 (2 (2 1)))</code>
|<code>(\1 1 1 1) (\\2 (2 (2 1)))</code>
|-
|-
|BBL(11)
|BBL(12)
|<math>10 {\uparrow}^{3} 16</math>
|<math>10 {\uparrow}^{3} 16</math>
|<code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code>
|<code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code>
|-
|-
|BBL(12)
|BBL(13)
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{2} 6</math>
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{2} 6</math>
|<code>(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code>
|<code>(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code>
|-
|-
|BBL(13)
|BBL(14)
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 16</math>
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 16</math>
|<code>(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)</code>
|<code>(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)</code>
|-
|-
|BBL(14)
|BBL(15)
|<math>f_{\omega+1}(10^{10^{19,727}})</math>
|<math>f_{\omega+1}(10^{10^{19,727}})</math>
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code>
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code>
|-
|-
|BBL(22)
|BBL(23)
|<math>f_{\omega^2}(4)</math>
|<math>f_{\omega^2}(4)</math>
|<code>(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 1))</code>
|<code>(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 1))</code>
|-
|-
|BBL(23)
|BBL(24)
|<math>f_{\omega^2}(27)</math>
|<math>f_{\omega^2}(27)</math>
|<code>(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 (2 1)))</code>
|<code>(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 (2 1)))</code>
|-
|-
|BBL(24)
|BBL(25)
|<math>f_{\omega^\omega}(4)</math>
|<math>f_{\omega^\omega}(4)</math>
|<code>(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))</code>
|<code>(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))</code>
|-
|-
|BBL(25)
|BBL(26)
|<math>f_{\omega^\omega}(27)</math>
|<math>f_{\omega^\omega}(27)</math>
|<code>(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))</code>
|<code>(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))</code>
|-
|BBL(27)
|<math>f_{\omega^\omega}(10^{12})</math>
|<code>(\1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))</code>
|-
|BBL(28)
|<math>f_{\omega^\omega}(10^{10^{12}})</math>
|<code>(\1 1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))</code>
|-
|BBL(34)
|<math>f_{\omega^{\omega^\omega}}(4)</math>
|<code>(\1 1 (\\\\1 4 3 2 1) (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))</code>
|}
|}


Line 443: Line 572:
!Lower Bound
!Lower Bound
!Champion
!Champion
|-
|TTBB(3)
|1
|<code>Δ: aa P: _</code>
|-
|-
|TTBB(4)
|TTBB(4)
|1
|1
|<code>Δ: aaa P: _</code>
|<code>Δ: aa P: a</code>
|-
|-
|TTBB(5)
|TTBB(5)
|2
|2
|<code>Δ: aaaa P: _</code>
|<code>Δ: aaa P: a</code>
|-
|-
|TTBB(6)
|TTBB(6)
|2
|3
|<code>Δ: aaaaa P: _</code>
|<code>Δ: aaaa P: a</code>
|-
|-
|TTBB(7)
|TTBB(7)
|3
|4
|<code>Δ: aaaaaa P: _</code>
|<code>Δ: aaaaa P: a</code>
|-
|-
|TTBB(8)
|TTBB(8)
|4
|5
|<code>Δ: aaaa P: bb, _</code>
|<code>Δ: aaaaaa P: a</code>
|-
|-
|TTBB(9)
|TTBB(9)
|5
|8
|<code>Δ: aaaaa P: bb, _</code>
|<code>Δ: aaa P: bbb, a</code>
|-
|-
|TTBB(10)
|TTBB(10)
|6
|13
|<code>Δ: aaaaaa P: bb, _</code>
|<code>Δ: aaaa P: bbb, a</code>
|-
|-
|TTBB(11)
|TTBB(11)
|7
|20
|<code>Δ: aaaaaaa P: bb, _</code>
|<code>Δ: aaaaa P: bbb, a</code>
|-
|-
|TTBB(12)
|TTBB(12)
Line 636: Line 761:
|31,957,632
|31,957,632
|<code>[7/15, 4/3, 27/14, 5/2, 9/5]</code>
|<code>[7/15, 4/3, 27/14, 5/2, 9/5]</code>
|-
|BBf(22)
|<math>1.146 \times 10^{62}</math>
|<code>[1/12, 9/10, 14/3, 11/2, 5/7, 3/11]</code>
|}
|}


Line 641: Line 770:


=== Brainfuck ===
=== Brainfuck ===
Maximum number of steps (write cells and move head) done by a brainfuck program (with only <code>+-<>[]</code> symbols). Cells size are unbounded and can have negative values.
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 667: Line 797:
|-
|-
|BFBB(11)
|BFBB(11)
|24
|38
|<code>++++++[--+]</code>
|<code>+[[>]-<+<+]</code>
|-
|BFBB(12)
|30
|<code>+++++[---++]</code>
|}
|}


=== Boolfuck ===
=== Boolfuck ===
Maximum number of steps (flip cells and move head) done by a boolfuck program (with only <code>*<>[]</code> symbols).
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 735: Line 862:


=== BitChanger ===
=== BitChanger ===
Maximum number of steps (flip cells and move head) done by a bitchanger program (with only <code><}[]</code> symbols).
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 766: Line 894:


=== Bitter ===
=== Bitter ===
Maximum number of steps (flip cells and move head) done by a bitter program (with only <code><>[]</code> symbols).
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 796: Line 925:
|}
|}


== Register machines ==
== Minsky machines ==
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 802: Line 931:
!Champion
!Champion
|-
|-
|RBB(1)
|MBB(1)
|1
|1
|<code>A- > H, 1</code>
|<code>0+Z</code>
|-
|-
|RBB(2)
|MBB(2)
|3
|3
|<code>A- > H, 2 / A+ > 1</code>
|<code>0+B_0-B*</code>
|-
|-
|RBB(3)
|MBB(3)
|5
|5
|<code>A+ > 2 / B- > H, 3 / B+ > 1</code>
|<code>0+B_0+C_0-C*</code>
|-
|-
|RBB(4)
|MBB(4)
|8
|10
|<code>B+ > 2 / B+ > 3 / A+ > 4 / B- > 3, H</code>
|<code>0+B_1+C_0-BD_1-C*</code>
|-
|-
|RBB(5)
|MBB(5)
|11
|24
|<code>B+ > 2 / B+ > 3 / A+ > 4 / A+ > 5 / B- > 3, H</code>
|<code>0-DB_0+C_1-ED_1+A_1-B*</code>
|-
|-
|RBB(6)
|MBB(6)
|15
|49
|<code>B+ > 2 / B+ > 3 / B+ > 4 / A+ > 5 / A+ > 6 / B- > 4, H</code>
|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
|}
|}

Latest revision as of 20:39, 20 December 2025

This is a list of Busy Beaver functions for Turing machines and other simple Turing-complete systems and their current lower bounds.

I only add functions that follow the requirements below:

  • The function must grow uncomputably fast, like BB(n).
  • The function must not grow uncomputably faster than BB(n), like BBB(n).
  • The function must not have similar champions to other function, like Σ(n).
  • The function must not be unecessary complex.

Turing machines

Classic

Maximum number of steps done by a n-state, m-symbol Turing Machine with k+1 undefined transitions before halting. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BB(2,2,1) 4 0RB---_1LA--- (bbch)
BB(2,2) 6 1RB1LB_1LA--- (bbch)
BB(2,3,1) 14 0RB---1LB_1LA2RB--- (bbch)
BB(3,2,1) 17 1RB---_0RC---_1LC0LA (bbch)
BB(3,2) 21 1RB---_1LB0RC_1LC1LA (bbch)
BB(2,3) 38 1RB2LB---_2LA2RB1LB (bbch)
BB(4,2,1) 38 1RB---_1LB0LC_1RD1LD_0RB--- (bbch)
BB(3,3,2) 77 1RB---0RC_2LC------_2RC0LC1RA (bbch)
BB(4,2) 107 1RB1LB_1LA0LC_---1LD_1RD0RA (bbch)
BB(2,4,1) 124 1RB3LA1RA0LA_2LA------3RA (bbch)
BB(5,2,1) 139 1RB1LB_1LA0LC_---1LD_1RE1LE_---0RA (bbch)
BB(2,4) 3,932,964 1RB2LA1RA1RA_1LB1LA3RB--- (bbch)
BB(3,3,1) 3,932,964 1RB2LA1RA_1LC1LA2RB_---1LA--- (bbch)
BB(5,2) 47,176,870 1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA (bbch)
BB(6,2,1) 17,397,627,083 1RB0LA_1RC1RD_1LB1RA_---0RE_1LF0RC_1LA--- (bbch)
BB(3,3) 1.191×1017 0RB2LA1RA_1LA2RB1RC_---1LB1LC (bbch)
BB(2,5) 10↑10↑10↑3,314,360 1RB3LA4RB0RB2LA_1LB2LA3LA1RA--- (bbch)
BB(2,6) 10↑210↑21010115 1RB3RB5RA1LB5LA2LB_2LA2RA4RB---3LB2LA (bbch)
BB(6,2) 10↑210↑210↑28 1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch)
BB(4,3) 10↑310↑310↑31028 1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD (bbch)
BB(7,2) 10↑1110↑104 1RB0RA_1LC1LF_1RD0LB_1RA1LE_---0LC_1RG1LD_0RG0RF (bbch)
BB(3,4) 10↑154 1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(9,2) fω(10↑710↑72) 1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH (bbch)
BB(3,5) fω(10↑154) 1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC (bbch)
BB(10,2) fω2(25) 1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch)
BB(11,2) fω2(10↑210) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE (bbch)
BB(12,2) fω4(10↑265,534) 0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL (bbch)
BB(14,2) fω+1(65,536) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ--- (bbch)
BB(15,2) fω+1(fω(1057)) 0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch)
BB(16,2) fω+12(101057) 0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP (bbch)
BB(2,7)

Blanking

Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.

Domain Lower Bound Champion
BLB(2,2,1) 3 1RB0LA_0LA--- (bbch)
BLB(2,2) 8 1RB0RA_1LB1LA (bbch)
BLB(3,2) 34 1RB1LB_1LA1LC_1RC0LC (bbch)
BLB(2,3) 77 1RB2LA0RB_1LA0LB1RA (bbch)
BLB(4,2) 32,779,477 1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch)
BLB(5,2) 32,810,047 1RB1LC_1RD0LE_0RD0RC_1LD1LA_1RB1RE (bbch)
BLB(6,2) 65,538,549 1RB1LE_1RD1RB_0RD0RE_1LD1LA_0RF1RF_0LC1LC (bbch)
BLB(2,4) 1.367×1012 1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)

Reversible

Maximum number of steps done by a n-state, m-symbol reversible Turing Machine with k+1 undefined transitions before halting.

Domain Lower Bound Champion
BBr(2,2,1) 4 0RB---_1LA--- (bbch)
BBr(2,2) 6 0RB---_1LA1RB (bbch)
BBr(3,2) 17 0RB---_0LC1RA_1RB1LC (bbch)
BBr(4,2) 48 1RB0LD_0LC0RB_1LA1LD_1LC--- (bbch)
BBr(5,2) 388 1RB0RD_1RC0RB_1RD---_1LE1LA_0LE0LA (bbch)
BBr(6,2) 537,556 1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA---_1RF1RA (bbch)
BBr(7,2) 1019 1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB--- (bbch)

Consecutive ones

Maximum number of consecutive 1s left on the tape by a n-state, m-symbol Turing Machine with k+1 undefined transitions after halting. TMs must leave all their 1s consecutively.

Domain Lower Bound Champion
BBn(2,2,1) 2 1RB---_1LA--- (bbch)
BBn(2,2) 4 1RB1LB_1LA--- (bbch)
BBn(2,3) 5 1RB1LB_1RC1LC_1LA--- (bbch)
BBn(3,2) 6 1RB1LC_1RC---_1LA0LB (bbch)
BBn(4,2) 12 1RB0LA_1RC1LB_1LB1RD_---0RA (bbch)
BBn(3,3) 12 1RB1RA---_1LC1LC2LA_2RA1LB1LA (bbch)
BBn(5,2) 165 1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB (bbch)

Semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turing Machine with k undefined transitions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.

Domain Lower Bound Champion
BBt(2,2,1) 3 1RB---_1LB0RB (bbch)
BBt(2,2) 3 1RB---_1LB0RB (bbch)
BBt(2,3,1) 9 1RB---2RB_2LB2RA0RB (bbch)
BBt(3,2,1) 11 1RB---_0RC0RB_1LB1LC (bbch)
BBt(3,2) 12 0RB0LB_0RC1RC_1LA0LC (bbch)
BBt(2,3) 17 1RB0RA0RB_2LA2RB1LB (bbch)
BBt(2,4,1) 22 3RB2LB1RB1RA_2LA2RB1LA--- (bbch)
BBt(4,2,1) 26 1RB---_1RC0LD_0RD0RC_1LC1LD (bbch)
BBt(2,4) 33 3RB2LB1RA2RB_3LB2RA1LA0RA (bbch)
BBt(4,2) 60 1RB1RC_0RD0RC_1RD1LD_1LA0LB (bbch)
BBt(3,3,2) 70 1RB---2RB_2RC---1RC_2LC2RA0RC (bbch)
BBt(3,3,1) 70 1RB---2RB_2RC---1RC_2LC2RA0RC (bbch)
BBt(3,3) 156 2RB0LA1RC_1LA2LB1RB_2LC0RC0RB (bbch)

Preperiodic

Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions before turning into a translated cycler.

Domain Lower Bound
BBS(2,2,1) 4 1RB---_1LB0RB (bbch)
BBS(2,2) 9 1RB0LB_1LA0RB (bbch)
BBS(3,2) 101 1RB1LB_0RC0LA_1LC0LA (bbch)
BBS(4,2) 119,120,230,102 1RB1LC_0LA1RD_0RB0LC_1LA0RD (bbch)
BBS(2,4) 2×1023 1RB2LA1RA1LB_0LB2RB3RB1LA (bbch)
BBP(5,2,1) 5.418×1051 1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC (bbch)
BBP(5,2) 1014,006 1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch)
BBP(3,3) 10↑26 1RB0LB2LA_1LA0RC0LB_2RC2RB0LC (bbch)

Periodic

Maximum translated cycler period done by a n-state, m-symbol Turing Machine with k undefined transitions.

Domain Lower Bound Champion
BBP(2,2,1) 3 1RB---_0LB1RA (bbch)
BBP(2,2) 9 1RB0RB_1LB1RA (bbch)
BBP(3,2) 92 1RB0LA_0RC1LA_1LC0RB (bbch)
BBP(3,3) 336 2RB0LA1RC_1LA2LB1RB_2LC0RC0RB (bbch)
BBP(2,4) 33,209,131 1RB0RA3LB1RB_2LA0LB1RA2RB (bbch)
BBP(4,2) 212,081,736 1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch)
BBP(5,2,1) 8,468,569,863 1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC (bbch)

Turmite

Maximum number of steps done by a n-state, m-symbol Turmite Machine with k+1 undefined transitions before halting.

Domain Lower Bound Champion
TT(2,2,1) 6 0PB---_1TA---
TT(2,2) 13 1TB---_1PA0PB
TT(2,3,1) 20 1TB------_1PA2PB0PB
TT(3,2,1) 20 1TB---_1PC0PB_1PA---
TT(3,2) 82 1PB0PA_1TA0PC_1PA---
TT(4,2,1) 95 1TB1PB_1PC---_0PA0TD_---0TB
TT(2,3) 223 1TB0PA2PA_2PA---1PA
TT(4,2) 758 1TB---_0PD1PB_1PA1TA_0PC0PD
TT(2,4) 1,068 1TB3TB2PB---_2TB1PA0PA2TB

Lambda calculus

SK calculus

Domain Lower Bound Champion
SKBB(4) 4 SSSS
SKBB(5) 6 SSS(SS)
SKBB(6) 8 SSS(SSS)
SKBB(7) 10 SSS(SSSS)
SKBB(8) 23 SSS(S(SKS))S

BCKW calculus

Domain Lower Bound Champion
BCKWBB(3) 3 BBB
BCKWBB(4) 5 WB(BB)
BCKWBB(5) 7 WB(BBB)
BCKWBB(6) 11 WB(WB(BB))
BCKWBB(7) 15 WB(WB(BBB))
BCKWBB(8) 23 WB(WB(WB(BB)))

De Bruijn

Domain Lower Bound Champion
BBL(7) 7 \1 1 1 1 1 1
BBL(8) 16 (\1 1) (\\2 (1 2))
BBL(9) 68 (\1 1) (\\2 (2 (1 2)))
BBL(10) 7.625×1012 (\1 1 1) (\\2 (2 (2 1)))
BBL(11) 107.625×1012 (\1 1 1 1) (\\2 (2 (2 1)))
BBL(12) 10↑316 (\1 1 1) (\1 (\\2 (2 1)) 1)
BBL(13) 10↑310↑310↑26 (\1 1) (\1 (\1 (\\2 (2 1)) 2))
BBL(14) 10↑310↑310↑316 (\1 1 1 1 1) (\1 (\\2 (2 1)) 1)
BBL(15) fω+1(101019,727) (\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))
BBL(23) fω2(4) (\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 1))
BBL(24) fω2(27) (\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 (2 1)))
BBL(25) fωω(4) (\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))
BBL(26) fωω(27) (\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(27) fωω(1012) (\1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(28) fωω(101012) (\1 1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(34) fωωω(4) (\1 1 (\\\\1 4 3 2 1) (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))

Tag system

2-tag system

Domain Lower Bound Champion
TTBB(4) 1 Δ: aa P: a
TTBB(5) 2 Δ: aaa P: a
TTBB(6) 3 Δ: aaaa P: a
TTBB(7) 4 Δ: aaaaa P: a
TTBB(8) 5 Δ: aaaaaa P: a
TTBB(9) 8 Δ: aaa P: bbb, a
TTBB(10) 13 Δ: aaaa P: bbb, a
TTBB(11) 20 Δ: aaaaa P: bbb, a
TTBB(12) 24 Δ: aaa P: bc, a, aaa

Cyclic tag

Domain Lower Bound Champion
CTBB(2) 1 Δ: 1 P: _
CTBB(3) 2 Δ: 11 P: _
CTBB(4) 4 Δ: 11 P: 0
CTBB(5) 6 Δ: 111 P: 0
CTBB(6) 9 Δ: 111 P: 00
CTBB(7) 12 Δ: 1111 P: 00
CTBB(8) 16 Δ: 1111 P: 000
CTBB(9) 20 Δ: 11111 P: 000
CTBB(10) 25 Δ: 11111 P: 0000

Tree rewrite

Domain Lower Bound Champion
TRBB(2) 1 Δ: () P: () > _
TRBB(3) 2 Δ: ()() P: () > _
TRBB(4) 3 Δ: ()()() P: () > _
TRBB(5) 4 Δ: ()()()() P: () > _
TRBB(6) 6 Δ: ()()() P: () > (), () > _
TRBB(7) 8 Δ: ()()()() P: () > (), () > _
TRBB(8) 10 Δ: ()()()()() P: () > (), () > _
TRBB(14) 38 Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
TRBB(23) 672 Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
TRBB(38) 10↑10↑10↑10↑54 Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
TRBB(45) 10↑3130 Δ: ((()))((())) P: ((())) > ((()))(()()), (()()) > (()())(()), (()) > (())(()()()), (()()()) > (()()())()(), ()()() > _, () > _
TRBB(69) 10↑410↑210↑24 Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _

Fractran

Domain Lower Bound Champion
BBf(10) 7 [729/2, 1/3]
BBf(11) 10 [27/2, 25/3, 1/5]
BBf(12) 13 [81/2, 25/3, 1/5]
BBf(13) 17 [81/2, 125/3, 1/5]
BBf(14) 21 [243/2, 125/3, 1/5]
BBf(15) 28 [1/45, 4/5, 3/2, 25/3]
BBf(16) 53 [1/45, 4/5, 3/2, 125/3]
BBf(17) 107 [5/6, 49/2, 3/5, 40/7]
BBf(18) 211 [5/6, 49/2, 3/5, 80/7]
BBf(19) 370 [5/6, 49/2, 3/5, 160/7]
BBf(20) 746 [7/15, 22/3, 6/77, 5/2, 9/5]
BBf(21) 31,957,632 [7/15, 4/3, 27/14, 5/2, 9/5]
BBf(22) 1.146×1062 [1/12, 9/10, 14/3, 11/2, 5/7, 3/11]

Brainfuck

Brainfuck

Maximum number of steps (write cells and move head) done by a brainfuck program (with only +-<>[] symbols). Cells size are unbounded and can have negative values.

Domain Lower Bound Champion
BFBB(6) 6 ++++++
BFBB(7) 8 ++++[-]
BFBB(8) 12 +++[--+]
BFBB(9) 16 ++++[--+]
BFBB(10) 20 +++++[--+]
BFBB(11) 38 +[[>]-<+<+]

Boolfuck

Maximum number of steps (flip cells and move head) done by a boolfuck program (with only *<>[] symbols).

Domain Lower Bound Champion
BLBB(7) 7 >>>>>>>
BLBB(8) 9 *>*[<<>]
BLBB(9) 11 *>>>*[<*]
BLBB(10) 14 *>*>*[<<>]
BLBB(11) 17 *>>>*[<<>*]
BLBB(12) 21 *>>>>*[<<>*]
BLBB(13) 25 *>>>>>*[<<>*]
BLBB(14) 58 +>+[<+<+[>]+<]
BLBB(17) 109 +>>+>>+[>>+[<]+<]
BLBB(19) 112 +>+>>+>>+[>>+[<]+<]
BLBB(20) 180 +>>+>>+>>+[>>+[<]+<]
BLBB(22) 183 +>+>>+>>+>>+[>>+[<]+<]
BLBB(23) 269 +>>+>>+>>+>>+[>>+[<]+<]

BitChanger

Maximum number of steps (flip cells and move head) done by a bitchanger program (with only <}[] symbols).

Domain Lower Bound Champion
BCBB(7) 7 }}}}}}}
BCBB(8) 9 }}}}<[<]
BCBB(9) 13 }}}<[}<<]
BCBB(10) 17 }}}}<[}<<]
BCBB(11) 21 }}}}}<[}<<]
BCBB(12) 25 }}}}}}<[}<<]

Bitter

Maximum number of steps (flip cells and move head) done by a bitter program (with only <>[] symbols).

Domain Lower Bound Champion
BTBB(7) 7 >>>>>>>
BTBB(8) 9 >>>><[<]
BTBB(9) 11 >>>>><[<]
BTBB(10) 13 >>>>>><[<]
BTBB(11) 15 >>>>>>><[<]
BTBB(12) 17 >>>>>>>><[<]

Minsky machines

Domain Lower Bound Champion
MBB(1) 1 0+Z
MBB(2) 3 0+B_0-B*
MBB(3) 5 0+B_0+C_0-C*
MBB(4) 10 0+B_1+C_0-BD_1-C*
MBB(5) 24 0-DB_0+C_1-ED_1+A_1-B*
MBB(6) 49 0+B_1-FC_1+D_0-CE_0+A_1-A*
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Azerty/Busy_Beaver_Functions&oldid=5709"