User:Azerty/Busy Beaver Functions: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
Azerty (talk | contribs)
231 edits
Created page with "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 will add more functions soon. == Turing Machines == {| class="wikitable" !Function !Value |- |BB(2) |6 |- |BB(3) |21 |- |BB(2,3) |38 |- |BB(4) |107 |- |..."
 
Azerty (talk | contribs)
231 edits
 
(137 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 meet the requirements below:


I will add more functions soon.
* The function must grow uncomputably fast, like BB(n).
* The function must not have similar champions to other function, like Σ(n).
* The function must not be arbitrary complex.


== Turing Machines ==
== Turing machines ==
 
=== [[Busy Beaver Functions|Classic]] ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs halt when they are on an undefined transititon.
{| class="wikitable"
{| class="wikitable"
!Function
!Domain
!Value
!Lower Bound
!Champion
|-
|BB(2,2,1)
|4
|{{TM|0RB_1LA|halt}}
|-
|-
|[[BB(2)]]
|[[BB(2)|BB(2,2)]]
|6
|6
|{{TM|1RB1LB_1LA---|halt}}
|-
|BB(2,3,1)
|14
|{{TM|0RB---1LB_1LA2RB---|halt}}
|-
|-
|[[BB(3)]]
|BB(3,2,1)
|17
|{{TM|1RB---_0RC---_1LC0LA|halt}}
|-
|[[BB(3)|BB(3,2)]]
|21
|21
|{{TM|1RB---_1LB0RC_1LC1LA|halt}}
|-
|-
|[[BB(2,3)]]
|[[BB(2,3)]]
|38
|38
|{{TM|1RB2LB---_2LA2RB1LB|halt}}
|-
|-
|[[BB(4)]]
|BB(4,2,1)
|38
|{{TM|1RB---_1LB0LC_1RD1LD_0RB---|halt}}
|-
|BB(3,3,2)
|77
|{{TM|1RB---0RC_2LC------_2RC0LC1RA|halt}}
|-
|[[BB(4)|BB(4,2)]]
|107
|107
|{{TM|1RB1LB_1LA0LC_---1LD_1RD0RA|halt}}
|-
|BB(2,4,1)
|124
|{{TM|1RB3LA1RA0LA_2LA------3RA|halt}}
|-
|BB(5,2,1)
|242
|{{TM|1RB0LA_1RC0LA_1LD0RE_---1LA_---0RB|halt}}
|-
|-
|[[BB(2,4)]]
|[[BB(2,4)]]
|3,932,964
|3,932,964
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---|halt}}
|-
|BB(3,3,1)
|3,932,964
|{{TM|1RB2LA1RA_1LC1LA2RB_---1LA---|halt}}
|-
|-
|[[BB(5)]]
|[[BB(5)|BB(5,2)]]
|47,176,870
|47,176,870
|{{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)]]
|<math>\geq 119\,112\,334\,170\,342\,541 > 10^{17}</math>
|<math>1.191 \times 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_---1LB1LC|halt}}
|-
|BB(3,4,2)
|<math>6.889 \times 10^{1,565}</math>
|{{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC|halt}}
|-
|[[BB(2,5)]]
|<math>10 \uparrow 10 \uparrow 10 \uparrow 3,314,360</math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA---|halt}}
|-
|[[BB(2,6)]]
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10^{10^{115}}</math>
|{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB---3LB2LA|halt}}
|-
|[[BB(6)|BB(6,2)]]
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 8</math>
|{{TM|1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|-
|-
|[[BB(4,3)]]
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 10^{28}</math>
|{{TM|1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD|halt}}
|-
|[[BB(7)|BB(7,2)]]
|<math>10 \uparrow^{11} 10 \uparrow^{10} 4</math>
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_---0LC_1RG1LD_0RG0RF|halt}}
|-
|[[BB(3,4)]]
|<math>10 \uparrow^{15} 4</math>
|{{TM|1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|-
|BB(9,2)
|<math>f_\omega(10 \uparrow^{7} 10 \uparrow^{7} 2)</math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
|-
|BB(3,5)
|<math>f_{\omega}(10 \uparrow^{15} 4)</math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC|halt}}
|-
|BB(10,2)
|<math>f_\omega^2(25)</math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|-
|BB(11,2)
|<math>f_\omega^2(10 {\uparrow}^{2} 10)</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|-
|BB(12,2)
|<math>f_{\omega}^4(10 {\uparrow}^{2} 65,534)</math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL|halt}}
|-
|BB(14,2)
|<math>f_{\omega + 1}(65,536)</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ---|halt}}
|-
|BB(15,2)
|<math>f_{\omega + 1}(f_\omega(10^{57}))</math>
|{{TM|0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN|halt}}
|-
|BB(16,2)
|<math>f_{\omega + 1}^2(10^{10^{57}})</math>
|{{TM|0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP|halt}}
|-
|[[BB(2,7)]]
|
|
|
|
|}
=== [[Instruction-Limited Busy Beaver|Instructions]] ===
Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBi(2)
|4
|{{TM|0RB_1LA|halt}}
|-
|BBi(3)
|6
|{{TM|1RB1LB_1LA---|halt}}
|-
|BBi(4)
|17
|{{TM|1RB---_0RC---_1LC0LA|halt}}
|-
|BBi(5)
|38
|{{TM|1RB2LB---_2LA2RB1LB|halt}}
|-
|BBi(6)
|124
|{{TM|1RB3LA1RA0LA_2LA------3RA|halt}}
|-
|BBi(7)
|3,932,964
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---|halt}}
|-
|BBi(8)
|<math>6.889 \times 10^{1,565}</math>
|{{TM|1RB1LA------_1RC3LB1RB---_2LA2LC---0LC|halt}}
|-
|BBi(9)
|<math>10 \uparrow 10 \uparrow 10 \uparrow 3,314,360</math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA---|halt}}
|-
|BBi(11)
|<math>10 \uparrow^{15} 4</math>
|{{TM|1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|-
|BB(14)
|<math>f_{\omega}(10 \uparrow^{15} 4)</math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC|halt}}
|-
|BBi(19)
|<math>f_\omega^2(25)</math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|-
|BBi(21)
|<math>f_\omega^2(10 {\uparrow}^{2} 10)</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE|halt}}
|-
|BBi(23)
|<math>f_{\omega}^4(10 {\uparrow}^{2} 65,534)</math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL|halt}}
|-
|BBi(27)
|<math>f_{\omega + 1}(65,536)</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ---|halt}}
|-
|BBi(29)
|<math>f_{\omega + 1}(f_\omega(10^{57}))</math>
|{{TM|0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN|halt}}
|-
|BBi(31)
|<math>f_{\omega + 1}^2(10^{10^{57}})</math>
|{{TM|0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP|halt}}
|}
=== Semi-infinite tape ===
Maximum number of right steps done by a n-state, m-symbol Turing machine with k undefined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|BBt(2,2,1)
|3
|{{TM|1RB---_1LB0RB|halt}}
|-
|BBt(2,2)
|3
|{{TM|1RB---_1LB0RB|halt}}
|-
|BBt(2,3,1)
|9
|{{TM|1RB---2RB_2LB2RA0RB|halt}}
|-
|BBt(3,2,1)
|11
|{{TM|1RB---_0RC0RB_1LB1LC|halt}}
|-
|BBt(3,2)
|12
|{{TM|0RB0LB_0RC1RC_1LA0LC|halt}}
|-
|BBt(2,3)
|17
|{{TM|1RB0RA0RB_2LA2RB1LB|halt}}
|-
|BBt(2,4,1)
|36
|{{TM|1RB3RA0RB0RA_2LA2RB1LB---|halt}}
|-
|BBt(2,4)
|49
|{{TM|1RB2RA2RB2LA_2LB0RA3RB0LA|halt}}
|-
|BBt(4,2,1)
|55
|{{TM|0RB---_1RC0LD_1RD1RB_1LB0RC|halt}}
|-
|BBt(4,2)
|63
|{{TM|0RB0LD_0RC1LC_0RD1LA_1LB1RD|halt}}
|-
|BBt(5,2,1)
|70
|{{TM|0RB---_0RC1LC_1RD0RE_1RE1RD_1LE1LB|halt}}
|-
|BBt(3,3,2)
|93
|{{TM|1RB------_0RC0RB1LC_1LB2RC0LB|halt}}
|-
|BBt(3,3)
|202
|{{TM|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB|halt}}
|-
|BBt(4,3,2)
|425
|{{TM|1RB------_1RC------_0RD0RC1LD_1LC2RD0LC|halt}}
|}
=== Semi-infinite tape instructions ===
Maximum number of right steps done by a Turing machine with n defined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|BBti(3)
|3
|{{TM|1RB---_1LB0RB|halt}}
|-
|BBti(4)
|8
|{{TM|1RB---_1RC---_1LC0RC|halt}}
|-
|BBti(5)
|18
|{{TM|1RB------_1RC------_2LC2RC0RC|halt}}
|-
|BBti(6)
|36
|{{TM|1RB------_1RC------_1RD------_2LD2RD0RD|halt}}
|-
|BBti(7)
|93
|{{TM|1RB------_0RC0RB1LC_1LB2RC0LB|halt}}
|-
|BBti(8)
|425
|{{TM|1RB------_1RC------_0RD0RC1LD_1LC2RD0LC|halt}}
|}
=== [[Blanking Busy Beaver Function|Blanking]] ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|BLB(2,2,1)
|4
|{{TM|1RB0RA_1LA---}}
|-
|BLB(2,2)
|8
|{{TM|1RB0RA_1LB1LA}}
|-
|BLB(3,2,1)
|16
|{{TM|1RB---_1LC0LC_1RC0LB}}
|-
|BLB(2,3,1)
|22
|{{TM|1RB2LB---_2LA0RB1LB}}
|-
|BLB(3,2)
|34
|{{TM|1RB1LB_1LA1LC_1RC0LC}}
|-
|BLB(2,3)
|77
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|-
|BLB(4,2,1)
|169
|{{TM|1RB---_0RC0LA_1LC1LD_0RB0RD}}
|-
|BLB(3,3,2)
|173
|{{TM|1RB------_2RC2RB1LB_2LC2RB0RC}}
|-
|BLB(3,3,1)
|308
|{{TM|1RB1RC---_1LB1RA2RB_0RB2LC0RC}}
|-
|BLB(4,2)
|32,779,477
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
|-
|BLB(5,2)
|32,810,047
|{{TM|1RB1LC_1RD0LE_0RD0RC_1LD1LA_1RB1RE}}
|-
|BLB(6,2)
|65,538,549
|{{TM|1RB1LE_1RD1RB_0RD0RE_1LD1LA_0RF1RF_0LC1LC}}
|-
|BLB(2,4)
|<math>1.367 \times 10^{12}</math>
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}}
|}
=== [[Blanking Busy Beaver Function#Instruction-limited Blanking Busy Beaver (BLBi(n))|Blanking instructions]] ===
Maximum number of steps done by a Turing machine with n defined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|BLBi(3)
|4
|{{TM|1RB0RA_1LA---}}
|-
|BLBi(4)
|12
|{{TM|1RB---_1RC---_1LC0RC}}
|-
|BLBi(5)
|30
|{{TM|1RB------_1RC------_2LC2RC0RC}}
|-
|BLBi(6)
|77
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|-
|BLBi(7)
|173
|{{TM|1RB------_2RC2RB1LB_2LC2RB0RC}}
|-
|BLBi(8)
|<math>1.367 \times 10^{12}</math>
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}}
|}
=== Restricted move per state ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBms(2,2,1)
|4
|{{TM|0RB_1LA|halt}}
|-
|BBms(2,2)
|6
|{{TM|1RB---_1LB1LA}}
|-
|BBms(3,2,1)
|17
|{{TM|1RB---_0RC---_1LC0LA|halt}}
|-
|BBms(3,2)
|19
|{{TM|1RB1RA_0RC---_1LC0LA}}
|-
|BBms(4,2,1)
|32
|{{TM|1RB---_1LC---_0LD0LC_1RD0RA}}
|-
|BBms(4,2)
|75
|{{TM|1RB0RD_0RC0RA_1LC0LA_0RB---}}
|-
|BBms(5,2,1)
|87
|{{TM|1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA}}
|-
|BBms(5,2)
|422
|{{TM|1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB}}
|}
=== Restricted move per state instructions ===
Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBmsi(2)
|4
|{{TM|0RB_1LA|halt}}
|-
|BBmsi(3)
|6
|{{TM|1RB---_1LB1LA}}
|-
|BBmsi(4)
|17
|{{TM|1RB---_0RC---_1LC0LA|halt}}
|-
|BBmsi(5)
|23
|{{TM|1RB------_0RC------_1LC2LB0LA}}
|-
|BBmsi(6)
|66
|{{TM|1RB------_1LB0LC---_1RC2RA1RB}}
|-
|BBmsi(7)
|75
|{{TM|1RB0RD_0RC0RA_1LC0LA_0RB---}}
|-
|BBmsi(8)
|87
|{{TM|1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA}}
|-
|BBmsi(9)
|422
|{{TM|1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB}}
|}
=== Restricted write per state ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must write the same symbol per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBws(2)
|6
|{{TM|1RB1LB_1LA---}}
|-
|BBws(3)
|20
|{{TM|1RB---_0LC0RC_1LC1LA}}
|-
|BBws(4)
|53
|{{TM|1RB1LB_1LC1RD_1RA1LA_---0RC}}
|-
|BBws(5)
|422
|{{TM|1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB}}
|}
=== Restricted move and write per state ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must write the same symbol and go to the same direction per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBwsms(2)
|6
|{{TM|1RB---_1LB1LA}}
|-
|BBwsms(3)
|17
|{{TM|1RB---_0RC0RC_1LC1LA}}
|-
|BBwsms(4)
|29
|{{TM|1RB1RD_0LC0LA_1LC1LA_0RC---}}
|-
|BBwsms(5)
|422
|{{TM|1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB}}
|}
=== [[Reversible Turing Machine|Reversible]] ===
Maximum number of steps done by a n-state, m-symbol reversible Turing machine with k+1 instructions transitions before halting.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBr(2,2,1)
|4
|{{TM|0RB---_1LA---|halt}}
|-
|BBr(2,2)
|6
|{{TM|0RB---_1LA1RB|halt}}
|-
|BBr(3,2)
|17
|{{TM|0RB---_0LC1RA_1RB1LC|halt}}
|-
|BBr(4,2)
|48
|{{TM|1RB0LD_0LC0RB_1LA1LD_1LC---|halt}}
|-
|BBr(5,2)
|388
|{{TM|1RB0RD_1RC0RB_1RD---_1LE1LA_0LE0LA|halt}}
|-
|BBr(6,2)
|537,556
|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA---_1RF1RA|halt}}
|-
|BBr(7,2)
|<math>10^{19}</math>
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB---|halt}}
|}
=== [[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 instructions after halting. TMs must leave all their 1s consecutively.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBn(2,2,1)
|2
|{{TM|1RB---_1LA---|halt}}
|-
|BBn(2,2)
|4
|{{TM|1RB1LB_1LA---|halt}}
|-
|BBn(3,2)
|6
|{{TM|1RB1LC_1RC---_1LA0LB|halt}}
|-
|BBn(2,3)
|9
|{{TM|1RB2LB---_2LA2RB1LB|halt}}
|-
|BBn(4,2)
|12
|{{TM|1RB0LA_1RC1LB_1LB1RD_---0RA|halt}}
|-
|BBn(3,3)
|12
|{{TM|1RB1RA---_1LC1LC2LA_2RA1LB1LA|halt}}
|-
|BBn(5,2)
|165
|{{TM|1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB|halt}}
|-
|BBn(4,3)
|<math>10 {\uparrow}^{4} 4</math>
|{{TM|1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD|halt}}
|}
=== [[Non-halting Turing machine#Translated cycler preperiod|Preperiodic]] ===
Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions before turning into a translated cycler.
{| class="wikitable"
!Domain
!Lower Bound
!
|-
|BBS(2,2,1)
|4
|{{TM|1RB---_1LB0RB}}
|-
|BBS(2,2)
|9
|{{TM|1RB0LB_1LA0RB}}
|-
|BBS(3,2)
|101
|{{TM|1RB1LB_0RC0LA_1LC0LA}}
|-
|BBS(4,2)
|119,120,230,102
|{{TM|1RB1LC_0LA1RD_0RB0LC_1LA0RD}}
|-
|BBS(2,4)
|<math>2 \times 10^{23}</math>
|{{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}}
|}
=== [[Non-halting Turing machine#Translated cycler period|Periodic]] ===
Maximum translated cycler period done by a n-state, m-symbol Turing Machine with k undefined instructions.
{| class="wikitable"
!Domain
!Lower Bound
!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)
|1,195
|{{TM|1RB2RC1LC_0RC0RB1LA_2LA2RC1LB}}
|-
|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}}
|}
== Turing machine variations ==
=== [[Terminating Turmite|Turmite]] ===
Maximum number of steps done by a n-state, m-symbol Turmite machine with k+1 undefined instructions before halting.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TT(2,2,1)
|6
|<code>0PB_1TA</code>
|-
|TT(2,2)
|13
|<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)
|139
|<code>1PB---_0PD0TC_---0TA_1TA1PA</code>
|-
|TT(2,3)
|223
|<code>1TB0PA2PA_2PA---1PA</code>
|-
|TT(3,3,1)
|683
|<code>1TB0PA---_1PC1PB0TC_2PA1PA---</code>
|-
|TT(4,2)
|758
|<code>1TB---_0PD1PB_1PA1TA_0PC0PD</code>
|-
|TT(2,4)
|1,068
|<code>1TB3TB2PB---_2TB1PA0PA2TB</code>
|-
|TT(3,3)
|45,153
|<code>1PB1PA1TA_2TB2PB2PC_---2PA1TC</code>
|}
=== Turmite instructions ===
Maximum number of steps done by a Turmite machine with n defined instructions before halting.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TTi(2)
|6
|<code>0PB_1TA</code>
|-
|TTi(3)
|13
|<code>1TB---_1PA0PB</code>
|-
|TTi(4)
|20
|<code>1TB------_1PA2PB0PB</code>
|-
|TTi(5)
|223
|<code>1TB0PA2PA_2PA---1PA</code>
|-
|TTi(7)
|1,068
|<code>1TB3TB2PB---_2TB1PA0PA2TB</code>
|-
|TTi(8)
|45,153
|<code>1PB1PA1TA_2TB2PB2PC_---2PA1TC</code>
|}
=== Turmite semi-infinite tape ===
Maximum number of right steps done by a n-state, m-symbol Turmite machine with k undefined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|TTt(2,2,1)
|3
|<code>0PB---_1TB1PB</code>
|-
|TTt(2,2)
|4
|<code>1PB0TB_1TA0PB</code>
|-
|TTt(2,3,1)
|9
|<code>1PB2TB---_1TA0PB0TB</code>
|-
|TTt(3,2,1)
|9
|<code>0PB---_1PC1TC_1TB0PC</code>
|-
|TTt(3,2)
|23
|<code>0PB0PC_1PC0TA_1TB1TC</code>
|-
|TTt(2,3)
|39
|<code>2PB1TA1TB_2TA0TA0PB</code>
|-
|TTt(2,4,1)
|44
|<code>1PB2PB0PB---_2TB2TA3TA1TB</code>
|-
|TTt(4,2,1)
|48
|<code>0PB---_1TB1PC_0TB1TD_0PC0PD</code>
|-
|TTt(3,3,2)
|70
|<code>1PB---0PB_0PC---1PC_2TC0TA2PC</code>
|-
|TTt(3,3,1)
|82
|<code>1PB---1TC_2PC1TA0PB_2TB2TC2PB</code>
|-
|TTt(3,3)
|134
|<code>1PB2PC2TB_1TC0TA0PB_2TC1TA2TA</code>
|-
|TTt(4,2)
|166
|<code>1PB0TB_0PC0TA_0PD0PB_1TB1TA</code>
|-
|TTt(2,4)
|194
|<code>0PB2PB3TB0PA_1TB2TB3PB3TA</code>
|}
=== Turmite semi-infinite tape instructions ===
Maximum number of right steps done by a Turmite machine with n defined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|TTti(3)
|3
|<code>0PB---_1TB1PB</code>
|-
|TTti(4)
|8
|<code>0PB---_0PC---_1TC1PC</code>
|-
|TTti(5)
|21
|<code>0PB---_0PC---_0PD---_1TC0TD</code>
|-
|TTti(6)
|39
|<code>2PB1TA1TB_2TA0TA0PB</code>
|-
|TTti(7)
|70
|<code>1PB---0PB_0PC---1PC_2TC0TA2PC</code>
|-
|TTti(8)
|194
|<code>0PB2PB3TB0PA_1TB2TB3PB3TA</code>
|}
=== Turmite blanking ===
Maximum number of steps done by a n-state, m-symbol Turmite machine with k undefined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|TLT(2,2,1)
|7
|<code>1TB0TB_0PA---</code>
|-
|TLT(2,2)
|12
|<code>1PB0PA_1TA0TA</code>
|-
|TLT(2,3,1)
|24
|<code>1TB2PB0PA_2TA---0TA</code>
|-
|TLT(3,2,1)
|24
|<code>1PB---_0PC0TC_1TA0TA</code>
|-
|TLT(3,2)
|84
|<code>1TB1PC_1TA0PA_1PA0TB</code>
|-
|TLT(4,2,1)
|84
|<code>1TB1PC_1TA0PA_1PA0TB</code>
|-
|TLT(2,3)
|108
|<code>1TB0TA0PB_2PA2PB0PA</code>
|-
|TLT(4,2)
|267
|<code>1TB0TD_1PC0PA_0PA0TD_1PD0PB</code>
|-
|TLT(2,4)
|357
|<code>1TB2TB0TB2PA_3TA2PA0PA3PB</code>
|-
|TLT(3,3)
|2,122
|<code>1TB2PA0TA_1TA0TB2PC_2PB0PA0TC</code>
|}
=== Turmite blanking instructions ===
Maximum number of steps done by a turmite machine with n defined instructions 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"
!Domain
!Lower Bound
!Champion
|-
|TLTi(3)
|7
|<code>1TB0TB_0PA---</code>
|-
|TLTi(4)
|12
|<code>1PB0PA_1TA0TA</code>
|-
|TLTi(5)
|24
|<code>1TB2PB0PA_2TA---0TA</code>
|-
|TLTi(6)
|108
|<code>1TB0TA0PB_2PA2PB0PA</code>
|-
|TLTi(8)
|357
|<code>1TB2TB0TB2PA_3TA2PA0PA3PB</code>
|-
|TLTi(9)
|2,122
|<code>1TB2PA0TA_1TA0TB2PC_2PB0PA0TC</code>
|}
=== Turmite restricted move per state ===
Maximum number of steps done by a n-state, m-symbol turmite machine with k+1 undefined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TTms(2,2,1)
|4
|<code>1TA0TB</code>
|-
|TTms(2,2)
|10
|<code>1TA1TB_---0PA</code>
|-
|TTms(3,2,1)
|12
|<code>1TA1TB_---0PC_0PA---</code>
|-
|TTms(3,2)
|25
|<code>1TA1TB_0PC0PA_---0PA</code>
|-
|TTms(4,2,1)
|30
|<code>1TA1TB_1PD0PC_0PA---_0PB---</code>
|-
|TTms(4,2)
|247
|<code>1TA1TB_0PD0PC_0PA0PB_0PC---</code>
|}
=== Turmite restricted move per state instructions ===
Maximum number of steps done by a turmite machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TTmsi(2)
|4
|<code>1TA0TB</code>
|-
|TTmsi(3)
|10
|<code>1TA1TB_---0PA</code>
|-
|TTmsi(4)
|16
|<code>1TA1TB_2PB0PA</code>
|-
|TTmsi(5)
|26
|<code>1TA1TB0TA_2PB0PA---</code>
|-
|TTmsi(6)
|36
|<code>1TA1TB0TC_2PB0PA---_0TB------</code>
|-
|TTmsi(7)
|247
|<code>1TA1TB_0PD0PC_0PA0PB_0PC---</code>
|}
== Lambda calculus ==
=== [[Busy Beaver for SKI calculus#SK calculus|SK calculus]] ===
Maximum normal form size of any closed SK term of size n.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|SKBB(4)
|4
|<code>SSSS</code>
|-
|SKBB(5)
|6
|<code>SSS(SS)</code>
|-
|SKBB(6)
|8
|<code>SSS(SSS)</code>
|-
|SKBB(7)
|10
|<code>SSS(SSSS)</code>
|-
|SKBB(8)
|23
|<code>SSS(S(SKS))S</code>
|}
=== BCKW calculus ===
Maximum normal form size of any closed BCKW term of size n.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BCKWBB(3)
|3
|<code>BBB</code>
|-
|BCKWBB(4)
|5
|<code>WB(BB)</code>
|-
|BCKWBB(5)
|7
|<code>WB(BBB)</code>
|-
|BCKWBB(6)
|11
|<code>WB(WB(BB))</code>
|-
|BCKWBB(7)
|15
|<code>WB(WB(BBB))</code>
|-
|BCKWBB(8)
|23
|<code>WB(WB(WB(BB)))</code>
|}
=== [[Busy Beaver for lambda calculus#De Bruijn|De Bruijn]] ===
Maximum normal form size of any closed lambda term of size n.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBL(7)
|7
|<code>\1 1 1 1 1 1</code>
|-
|BBL(8)
|16
|<code>(\1 1) (\\2 (1 2))</code>
|-
|BBL(9)
|68
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|-
|BBL(10)
|<math>7.625 \times 10^{12}</math>
|<code>(\1 1 1) (\\2 (2 (2 1)))</code>
|-
|BBL(11)
|<math>10^{7.625 \times 10^{12}}</math>
|<code>(\1 1 1 1) (\\2 (2 (2 1)))</code>
|-
|BBL(12)
|<math>10 {\uparrow}^{3} 16</math>
|<code>(\1 1 1) (\1 (\\2 (2 1)) 1)</code>
|-
|BBL(13)
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{2} 6</math>
|<code>(\1 1) (\1 (\1 (\\2 (2 1)) 2))</code>
|-
|BBL(14)
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 16</math>
|<code>(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)</code>
|-
|BBL(15)
|<math>f_{\omega+1}(10^{10^{19,727}})</math>
|<code>(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))</code>
|-
|BBL(18)
|<math>f_{\omega^{\omega^\omega}}(10^{19,727})</math>
|<code>(\1 1 1 1 1) (\\\1 (\\2 (2 1)) 3 2 1)</code>
|-
|BBL(23)
|<math>f_{\omega^{\omega^\omega}}(f_{\omega^{\omega+2}}(2))</math>
|<code>(\1 (\1 (\\\\1 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))</code>
|-
|BBL(24)
|<math>f_{\zeta_0}(15)</math>
|<code>(\1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 (2 1)))</code>
|-
|BBL(25)
|<math>f_{\psi(\Omega_\omega)}(12)</math>
|<code>(\1 1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 (2 1)))</code>
|-
|BBL(26)
|<math>f_{\psi(\Omega_\omega)}(f_{\omega^{\omega+2}}(2))</math>
|<code>(\1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 (2 1)))</code>
|-
|BBL(27)
|<math>f_{\psi(\Omega_\omega+1)}(4)</math>
|<code>(\1 1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 (2 1)))</code>
|}
== Tag system ==
=== 2-tag system ===
Maximum number of transformations performed with a 2-tag system of size n. Its size if the sum of the number of letters and the number of different letters.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TTBB(4)
|1
|<code>Δ: aa P: a</code>
|-
|TTBB(5)
|2
|<code>Δ: aaa P: a</code>
|-
|TTBB(6)
|3
|<code>Δ: aaaa P: a</code>
|-
|TTBB(7)
|4
|<code>Δ: aaaaa P: a</code>
|-
|TTBB(8)
|5
|<code>Δ: aaaaaa P: a</code>
|-
|TTBB(9)
|8
|<code>Δ: aaa P: bbb, a</code>
|-
|TTBB(10)
|13
|<code>Δ: aaaa P: bbb, a</code>
|-
|TTBB(11)
|20
|<code>Δ: aaaaa P: bbb, a</code>
|-
|TTBB(12)
|24
|<code>Δ: aaa P: bc, a, aaa</code>
|}
=== Cyclic tag ===
Maximum number of transformations that can be done with a cyclic tag system of size n. Its size if the sum of the number of bits and the number of instructions.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|CTBB(2)
|1
|<code>Δ: 1 P: _</code>
|-
|CTBB(3)
|2
|<code>Δ: 11 P: _</code>
|-
|CTBB(4)
|4
|<code>Δ: 11 P: 0</code>
|-
|CTBB(5)
|6
|<code>Δ: 111 P: 0</code>
|-
|CTBB(6)
|9
|<code>Δ: 111 P: 00</code>
|-
|CTBB(7)
|12
|<code>Δ: 1111 P: 00</code>
|-
|CTBB(8)
|16
|<code>Δ: 1111 P: 000</code>
|-
|CTBB(9)
|20
|<code>Δ: 11111 P: 000</code>
|-
|CTBB(10)
|25
|<code>Δ: 11111 P: 0000</code>
|}
=== Tree rewriting ===
Maximum number of transformations that can be done with a tree rewriting system of size n. Its size if the number of brackets.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TRBB(2)
|1
|<code>Δ: () P: () > _</code>
|-
|TRBB(3)
|2
|<code>Δ: ()() P: () > _</code>
|-
|TRBB(4)
|3
|<code>Δ: ()()() P: () > _</code>
|-
|TRBB(5)
|4
|<code>Δ: ()()()() P: () > _</code>
|-
|-
|
|TRBB(6)
|
|6
|<code>Δ: ()()() P: () > (), () > _</code>
|-
|TRBB(7)
|8
|<code>Δ: ()()()() P: () > (), () > _</code>
|-
|TRBB(8)
|10
|<code>Δ: ()()()()() P: () > (), () > _</code>
|-
|TRBB(14)
|38
|<code>Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()</code>
|-
|TRBB(23)
|672
|<code>Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _</code>
|-
|TRBB(38)
|<math>10 \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 54</math>
|<code>Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _</code>
|-
|TRBB(45)
|<math>10 {\uparrow}^{3} 130</math>
|<code>Δ: ((()))((())) P: ((())) > ((()))(()()), (()()) > (()())(()), (()) > (())(()()()), (()()()) > (()()())()(), ()()() > _, () > _</code>
|-
|TRBB(69)
|<math>10 {\uparrow}^{4} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 4</math>
|<code>Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _</code>
|}
 
== Fractran ==
 
=== [[Fractran]] ===
Maximum number of instructions applied by a fractran program of size n before halting.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBf(10)
|7
|<code>[729/2, 1/3]</code>
|-
|BBf(11)
|10
|<code>[27/2, 25/3, 1/5]</code>
|-
|BBf(12)
|13
|<code>[81/2, 25/3, 1/5]</code>
|-
|BBf(13)
|17
|<code>[81/2, 125/3, 1/5]</code>
|-
|BBf(14)
|21
|<code>[243/2, 125/3, 1/5]</code>
|-
|BBf(15)
|28
|<code>[1/45, 4/5, 3/2, 25/3]</code>
|-
|BBf(16)
|53
|<code>[1/45, 4/5, 3/2, 125/3]</code>
|-
|BBf(17)
|107
|<code>[5/6, 49/2, 3/5, 40/7]</code>
|-
|BBf(18)
|211
|<code>[5/6, 49/2, 3/5, 80/7]</code>
|-
|BBf(19)
|370
|<code>[5/6, 49/2, 3/5, 160/7]</code>
|-
|BBf(20)
|746
|<code>[7/15, 22/3, 6/77, 5/2, 9/5]</code>
|-
|BBf(21)
|31,957,632
|<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>
|}
 
== Brainfuck ==
 
=== Brainfuck ===
Maximum number of instructions read by a brainfuck program with n instructions (uses <code>+-<>[]</code> symbols). Cells size are unbounded and can have negative values.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BFBB(6)
|6
|<code>++++++</code>
|-
|BFBB(7)
|8
|<code>++++[-]</code>
|-
|BFBB(8)
|12
|<code>+++[--+]</code>
|-
|BFBB(9)
|16
|<code>++++[--+]</code>
|-
|BFBB(10)
|20
|<code>+++++[--+]</code>
|-
|BFBB(11)
|38
|<code>+[[>]-<+<+]</code>
|}
 
=== Boolfuck ===
Maximum number of instructions read by a boolfuck program with n instructions (uses <code>*<>[]</code> symbols).
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BLBB(7)
|7
|<code>>>>>>>></code>
|-
|BLBB(8)
|9
|<code>*>*[<<>]</code>
|-
|BLBB(9)
|11
|<code>*>>>*[<*]</code>
|-
|BLBB(10)
|14
|<code>*>*>*[<<>]</code>
|-
|BLBB(11)
|17
|<code>*>>>*[<<>*]</code>
|-
|BLBB(12)
|21
|<code>*>>>>*[<<>*]</code>
|-
|BLBB(13)
|25
|<code>*>>>>>*[<<>*]</code>
|-
|BLBB(14)
|58
|<code>+>+[<+<+[>]+<]</code>
|-
|BLBB(17)
|109
|<code>+>>+>>+[>>+[<]+<]</code>
|-
|BLBB(19)
|112
|<code>+>+>>+>>+[>>+[<]+<]</code>
|-
|BLBB(20)
|180
|<code>+>>+>>+>>+[>>+[<]+<]</code>
|-
|BLBB(22)
|183
|<code>+>+>>+>>+>>+[>>+[<]+<]</code>
|-
|BLBB(23)
|269
|<code>+>>+>>+>>+>>+[>>+[<]+<]</code>
|}
 
=== BitChanger ===
Maximum number of instructions read by a bitchanger program with n instructions (uses <code><}[]</code> symbols).
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BCBB(7)
|7
|<code><nowiki>}}}}}}}</nowiki></code>
|-
|BCBB(8)
|9
|<code><nowiki>}}}}<[<]</nowiki></code>
|-
|BCBB(9)
|13
|<code><nowiki>}}}<[}<<]</nowiki></code>
|-
|BCBB(10)
|17
|<code><nowiki>}}}}<[}<<]</nowiki></code>
|-
|BCBB(11)
|21
|<code><nowiki>}}}}}<[}<<]</nowiki></code>
|-
|BCBB(12)
|25
|<code><nowiki>}}}}}}<[}<<]</nowiki></code>
|}
 
=== Bitter ===
Maximum number of instructions read by a bitter program with n instructions (uses <code><>[]</code> symbols).
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BTBB(7)
|7
|<code>>>>>>>></code>
|-
|BTBB(8)
|9
|<code>>>>><[<]</code>
|-
|BTBB(9)
|11
|<code>>>>>><[<]</code>
|-
|BTBB(10)
|13
|<code>>>>>>><[<]</code>
|-
|BTBB(11)
|15
|<code>>>>>>>><[<]</code>
|-
|BTBB(12)
|17
|<code>>>>>>>>><[<]</code>
|}
 
== Minsky machines ==
 
=== [[Register machine|Minsky machines]] ===
Maximum number of steps done by a Minsky machine before halting.
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|MBB(1)
|1
|<code>0+*</code>
|-
|MBB(2)
|3
|<code>0+B_0-B*</code>
|-
|MBB(3)
|5
|<code>0+B_0+C_0-C*</code>
|-
|-
|
|MBB(4)
|
|10
|<code>0+B_1+C_0-BD_1-C*</code>
|-
|-
|
|MBB(5)
|
|24
|<code>0-DB_0+C_1-ED_1+A_1-B*</code>
|-
|-
|
|MBB(6)
|
|49
|<code>0+B_1-FC_1+D_0-CE_0+A_1-A*</code>
|}
|}

Latest revision as of 09:58, 23 January 2026

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 meet the requirements below:

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

Turing machines

Classic

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions 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) 242 1RB0LA_1RC0LA_1LD0RE_---1LA_---0RB (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(3,4,2) 6.889×101,565 1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (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)

Instructions

Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BBi(2) 4 0RB_1LA (bbch)
BBi(3) 6 1RB1LB_1LA--- (bbch)
BBi(4) 17 1RB---_0RC---_1LC0LA (bbch)
BBi(5) 38 1RB2LB---_2LA2RB1LB (bbch)
BBi(6) 124 1RB3LA1RA0LA_2LA------3RA (bbch)
BBi(7) 3,932,964 1RB2LA1RA1RA_1LB1LA3RB--- (bbch)
BBi(8) 6.889×101,565 1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)
BBi(9) 10↑10↑10↑3,314,360 1RB3LA4RB0RB2LA_1LB2LA3LA1RA--- (bbch)
BBi(11) 10↑154 1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(14) fω(10↑154) 1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC (bbch)
BBi(19) fω2(25) 1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch)
BBi(21) fω2(10↑210) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE (bbch)
BBi(23) fω4(10↑265,534) 0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL (bbch)
BBi(27) fω+1(65,536) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ--- (bbch)
BBi(29) fω+1(fω(1057)) 0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch)
BBi(31) fω+12(101057) 0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP (bbch)

Semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turing machine with k undefined instructions 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) 36 1RB3RA0RB0RA_2LA2RB1LB--- (bbch)
BBt(2,4) 49 1RB2RA2RB2LA_2LB0RA3RB0LA (bbch)
BBt(4,2,1) 55 0RB---_1RC0LD_1RD1RB_1LB0RC (bbch)
BBt(4,2) 63 0RB0LD_0RC1LC_0RD1LA_1LB1RD (bbch)
BBt(5,2,1) 70 0RB---_0RC1LC_1RD0RE_1RE1RD_1LE1LB (bbch)
BBt(3,3,2) 93 1RB------_0RC0RB1LC_1LB2RC0LB (bbch)
BBt(3,3) 202 1RB2RC1LC_0RC0RB1LA_2LA2RC1LB (bbch)
BBt(4,3,2) 425 1RB------_1RC------_0RD0RC1LD_1LC2RD0LC (bbch)

Semi-infinite tape instructions

Maximum number of right steps done by a Turing machine with n defined instructions 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
BBti(3) 3 1RB---_1LB0RB (bbch)
BBti(4) 8 1RB---_1RC---_1LC0RC (bbch)
BBti(5) 18 1RB------_1RC------_2LC2RC0RC (bbch)
BBti(6) 36 1RB------_1RC------_1RD------_2LD2RD0RD (bbch)
BBti(7) 93 1RB------_0RC0RB1LC_1LB2RC0LB (bbch)
BBti(8) 425 1RB------_1RC------_0RD0RC1LD_1LC2RD0LC (bbch)

Blanking

Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions 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) 4 1RB0RA_1LA--- (bbch)
BLB(2,2) 8 1RB0RA_1LB1LA (bbch)
BLB(3,2,1) 16 1RB---_1LC0LC_1RC0LB (bbch)
BLB(2,3,1) 22 1RB2LB---_2LA0RB1LB (bbch)
BLB(3,2) 34 1RB1LB_1LA1LC_1RC0LC (bbch)
BLB(2,3) 77 1RB2LA0RB_1LA0LB1RA (bbch)
BLB(4,2,1) 169 1RB---_0RC0LA_1LC1LD_0RB0RD (bbch)
BLB(3,3,2) 173 1RB------_2RC2RB1LB_2LC2RB0RC (bbch)
BLB(3,3,1) 308 1RB1RC---_1LB1RA2RB_0RB2LC0RC (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)

Blanking instructions

Maximum number of steps done by a Turing machine with n defined instructions 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
BLBi(3) 4 1RB0RA_1LA--- (bbch)
BLBi(4) 12 1RB---_1RC---_1LC0RC (bbch)
BLBi(5) 30 1RB------_1RC------_2LC2RC0RC (bbch)
BLBi(6) 77 1RB2LA0RB_1LA0LB1RA (bbch)
BLBi(7) 173 1RB------_2RC2RB1LB_2LC2RB0RC (bbch)
BLBi(8) 1.367×1012 1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)

Restricted move per state

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BBms(2,2,1) 4 0RB_1LA (bbch)
BBms(2,2) 6 1RB---_1LB1LA (bbch)
BBms(3,2,1) 17 1RB---_0RC---_1LC0LA (bbch)
BBms(3,2) 19 1RB1RA_0RC---_1LC0LA (bbch)
BBms(4,2,1) 32 1RB---_1LC---_0LD0LC_1RD0RA (bbch)
BBms(4,2) 75 1RB0RD_0RC0RA_1LC0LA_0RB--- (bbch)
BBms(5,2,1) 87 1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA (bbch)
BBms(5,2) 422 1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted move per state instructions

Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BBmsi(2) 4 0RB_1LA (bbch)
BBmsi(3) 6 1RB---_1LB1LA (bbch)
BBmsi(4) 17 1RB---_0RC---_1LC0LA (bbch)
BBmsi(5) 23 1RB------_0RC------_1LC2LB0LA (bbch)
BBmsi(6) 66 1RB------_1LB0LC---_1RC2RA1RB (bbch)
BBmsi(7) 75 1RB0RD_0RC0RA_1LC0LA_0RB--- (bbch)
BBmsi(8) 87 1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA (bbch)
BBmsi(9) 422 1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted write per state

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must write the same symbol per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BBws(2) 6 1RB1LB_1LA--- (bbch)
BBws(3) 20 1RB---_0LC0RC_1LC1LA (bbch)
BBws(4) 53 1RB1LB_1LC1RD_1RA1LA_---0RC (bbch)
BBws(5) 422 1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted move and write per state

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must write the same symbol and go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
BBwsms(2) 6 1RB---_1LB1LA (bbch)
BBwsms(3) 17 1RB---_0RC0RC_1LC1LA (bbch)
BBwsms(4) 29 1RB1RD_0LC0LA_1LC1LA_0RC--- (bbch)
BBwsms(5) 422 1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Reversible

Maximum number of steps done by a n-state, m-symbol reversible Turing machine with k+1 instructions 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 instructions 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(3,2) 6 1RB1LC_1RC---_1LA0LB (bbch)
BBn(2,3) 9 1RB2LB---_2LA2RB1LB (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)
BBn(4,3) 10↑44 1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD (bbch)

Preperiodic

Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions 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 instructions.

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) 1,195 1RB2RC1LC_0RC0RB1LA_2LA2RC1LB (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)

Turing machine variations

Turmite

Maximum number of steps done by a n-state, m-symbol Turmite machine with k+1 undefined instructions 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) 139 1PB---_0PD0TC_---0TA_1TA1PA
TT(2,3) 223 1TB0PA2PA_2PA---1PA
TT(3,3,1) 683 1TB0PA---_1PC1PB0TC_2PA1PA---
TT(4,2) 758 1TB---_0PD1PB_1PA1TA_0PC0PD
TT(2,4) 1,068 1TB3TB2PB---_2TB1PA0PA2TB
TT(3,3) 45,153 1PB1PA1TA_2TB2PB2PC_---2PA1TC

Turmite instructions

Maximum number of steps done by a Turmite machine with n defined instructions before halting.

Domain Lower Bound Champion
TTi(2) 6 0PB_1TA
TTi(3) 13 1TB---_1PA0PB
TTi(4) 20 1TB------_1PA2PB0PB
TTi(5) 223 1TB0PA2PA_2PA---1PA
TTi(7) 1,068 1TB3TB2PB---_2TB1PA0PA2TB
TTi(8) 45,153 1PB1PA1TA_2TB2PB2PC_---2PA1TC

Turmite semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turmite machine with k undefined instructions 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
TTt(2,2,1) 3 0PB---_1TB1PB
TTt(2,2) 4 1PB0TB_1TA0PB
TTt(2,3,1) 9 1PB2TB---_1TA0PB0TB
TTt(3,2,1) 9 0PB---_1PC1TC_1TB0PC
TTt(3,2) 23 0PB0PC_1PC0TA_1TB1TC
TTt(2,3) 39 2PB1TA1TB_2TA0TA0PB
TTt(2,4,1) 44 1PB2PB0PB---_2TB2TA3TA1TB
TTt(4,2,1) 48 0PB---_1TB1PC_0TB1TD_0PC0PD
TTt(3,3,2) 70 1PB---0PB_0PC---1PC_2TC0TA2PC
TTt(3,3,1) 82 1PB---1TC_2PC1TA0PB_2TB2TC2PB
TTt(3,3) 134 1PB2PC2TB_1TC0TA0PB_2TC1TA2TA
TTt(4,2) 166 1PB0TB_0PC0TA_0PD0PB_1TB1TA
TTt(2,4) 194 0PB2PB3TB0PA_1TB2TB3PB3TA

Turmite semi-infinite tape instructions

Maximum number of right steps done by a Turmite machine with n defined instructions 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
TTti(3) 3 0PB---_1TB1PB
TTti(4) 8 0PB---_0PC---_1TC1PC
TTti(5) 21 0PB---_0PC---_0PD---_1TC0TD
TTti(6) 39 2PB1TA1TB_2TA0TA0PB
TTti(7) 70 1PB---0PB_0PC---1PC_2TC0TA2PC
TTti(8) 194 0PB2PB3TB0PA_1TB2TB3PB3TA

Turmite blanking

Maximum number of steps done by a n-state, m-symbol Turmite machine with k undefined instructions 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
TLT(2,2,1) 7 1TB0TB_0PA---
TLT(2,2) 12 1PB0PA_1TA0TA
TLT(2,3,1) 24 1TB2PB0PA_2TA---0TA
TLT(3,2,1) 24 1PB---_0PC0TC_1TA0TA
TLT(3,2) 84 1TB1PC_1TA0PA_1PA0TB
TLT(4,2,1) 84 1TB1PC_1TA0PA_1PA0TB
TLT(2,3) 108 1TB0TA0PB_2PA2PB0PA
TLT(4,2) 267 1TB0TD_1PC0PA_0PA0TD_1PD0PB
TLT(2,4) 357 1TB2TB0TB2PA_3TA2PA0PA3PB
TLT(3,3) 2,122 1TB2PA0TA_1TA0TB2PC_2PB0PA0TC

Turmite blanking instructions

Maximum number of steps done by a turmite machine with n defined instructions 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
TLTi(3) 7 1TB0TB_0PA---
TLTi(4) 12 1PB0PA_1TA0TA
TLTi(5) 24 1TB2PB0PA_2TA---0TA
TLTi(6) 108 1TB0TA0PB_2PA2PB0PA
TLTi(8) 357 1TB2TB0TB2PA_3TA2PA0PA3PB
TLTi(9) 2,122 1TB2PA0TA_1TA0TB2PC_2PB0PA0TC

Turmite restricted move per state

Maximum number of steps done by a n-state, m-symbol turmite machine with k+1 undefined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
TTms(2,2,1) 4 1TA0TB
TTms(2,2) 10 1TA1TB_---0PA
TTms(3,2,1) 12 1TA1TB_---0PC_0PA---
TTms(3,2) 25 1TA1TB_0PC0PA_---0PA
TTms(4,2,1) 30 1TA1TB_1PD0PC_0PA---_0PB---
TTms(4,2) 247 1TA1TB_0PD0PC_0PA0PB_0PC---

Turmite restricted move per state instructions

Maximum number of steps done by a turmite machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain Lower Bound Champion
TTmsi(2) 4 1TA0TB
TTmsi(3) 10 1TA1TB_---0PA
TTmsi(4) 16 1TA1TB_2PB0PA
TTmsi(5) 26 1TA1TB0TA_2PB0PA---
TTmsi(6) 36 1TA1TB0TC_2PB0PA---_0TB------
TTmsi(7) 247 1TA1TB_0PD0PC_0PA0PB_0PC---

Lambda calculus

SK calculus

Maximum normal form size of any closed SK term of size n.

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

Maximum normal form size of any closed BCKW term of size n.

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

Maximum normal form size of any closed lambda term of size n.

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(18) fωωω(1019,727) (\1 1 1 1 1) (\\\1 (\\2 (2 1)) 3 2 1)
BBL(23) fωωω(fωω+2(2)) (\1 (\1 (\\\\1 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))
BBL(24) fζ0(15) (\1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 (2 1)))
BBL(25) fψ(Ωω)(12) (\1 1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 (2 1)))
BBL(26) fψ(Ωω)(fωω+2(2)) (\1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 (2 1)))
BBL(27) fψ(Ωω+1)(4) (\1 1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 (2 1)))

Tag system

2-tag system

Maximum number of transformations performed with a 2-tag system of size n. Its size if the sum of the number of letters and the number of different letters.

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

Maximum number of transformations that can be done with a cyclic tag system of size n. Its size if the sum of the number of bits and the number of instructions.

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 rewriting

Maximum number of transformations that can be done with a tree rewriting system of size n. Its size if the number of brackets.

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

Fractran

Maximum number of instructions applied by a fractran program of size n before halting.

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 instructions read by a brainfuck program with n instructions (uses +-<>[] 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 instructions read by a boolfuck program with n instructions (uses *<>[] 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 instructions read by a bitchanger program with n instructions (uses <}[] 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 instructions read by a bitter program with n instructions (uses <>[] 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

Minsky machines

Maximum number of steps done by a Minsky machine before halting.

Domain Lower Bound Champion
MBB(1) 1 0+*
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=6073"