User:Azerty/Busy Beaver Functions: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
Azerty (talk | contribs)
87 edits
No edit summary
Azerty (talk | contribs)
87 edits
 
(34 intermediate revisions by the same user not shown)
Line 3: Line 3:
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.
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 ==
 
== Turing Machines ==


=== Normal ===
=== Normal ===
Line 13: Line 11:
!Champion
!Champion
|-
|-
|[[BB(2)]]
|BB(2,2,1)
|4
|{{TM|0RB---_1LA---|halt}}
|-
|[[BB(2)|BB(2,2)]]
|6
|6
|{{TM|1RB1LB_1LA1RZ|halt}}
|{{TM|1RB1LB_1LA---|halt}}
|-
|BB(2,3,1)
|14
|{{TM|0RB---1LB_1LA2RB---|halt}}
|-
|BB(3,2,1)
|17
|{{TM|1RB---_0RC---_1LC0LA|halt}}
|-
|-
|[[BB(3)]]
|[[BB(3)|BB(3,2)]]
|21
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|{{TM|1RB---_1LB0RC_1LC1LA|halt}}
|-
|-
|[[BB(2,3)]]
|[[BB(2,3)]]
|38
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|{{TM|1RB2LB---_2LA2RB1LB|halt}}
|-
|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)|BB(4,2)]]
|107
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|{{TM|1RB1LB_1LA0LC_---1LD_1RD0RA|halt}}
|-
|BB(2[[BB(2)|,4]],1)
|124
|{{TM|1RB3LA1RA0LA_2LA------3RA|halt}}
|-
|BB(5,2,1)
|139
|{{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_1LB1LA3RB1RZ|halt}}
|{{TM|1RB2LA1RA1RA_1LB1LA3RB---|halt}}
|-
|-
|[[BB(5)]]
|[[BB(5)|BB(5,2)]]
|47,176,870
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA|halt}}
|-
|-
|[[BB(3,3)]]
|[[BB(3,3)]]
|<math>1.191 \times 10^{17}</math>
|<math>1.191 \times 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|{{TM|0RB2LA1RA_1LA2RB1RC_---1LB1LC|halt}}
|-
|-
|[[BB(2,5)]]
|[[BB(2,5)]]
|<math>10 {\uparrow}^{2} 3 \,|\, 3,314,360</math>
|<math>10 \uparrow 10 \uparrow 10 \uparrow 3,314,360</math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA---|halt}}
|-
|-
|[[BB(2,6)]]
|[[BB(2,6)]]
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10^{10^{115}}</math>
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10^{10^{115}}</math>
|{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA|halt}}
|{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB---3LB2LA|halt}}
|-
|-
|[[BB(6)]]
|[[BB(6)|BB(6,2)]]
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 8</math>
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 8</math>
|{{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|{{TM|1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|-
|-
|[[BB(4,3)]]
|[[BB(4,3)]]
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 10^{28}</math>
|<math>10 {\uparrow}^{3} 10 {\uparrow}^{3} 10 {\uparrow}^{3} 10^{28}</math>
|{{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD|halt}}
|{{TM|1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD|halt}}
|-
|-
|[[BB(7)]]
|[[BB(7)|BB(7,2)]]
|<math>10 \uparrow^{11} 10 \uparrow^{10} 4</math>
|<math>10 \uparrow^{11} 10 \uparrow^{10} 4</math>
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF|halt}}
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_---0LC_1RG1LD_0RG0RF|halt}}
|-
|-
|[[BB(3,4)]]
|[[BB(3,4)]]
|<math>10 \uparrow^{15} 4</math>
|<math>10 \uparrow^{15} 4</math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|{{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)
|BB(3,5)
|<math>f_{\omega}(10 \uparrow^{15} 4)</math>
|<math>f_{\omega}(10 \uparrow^{15} 4)</math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|{{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)]]
|[[BB(2,7)]]
Line 80: Line 138:
!Champion
!Champion
|-
|-
|BLB(2)
|BLB(2,2,1)
|3
|{{TM|1RB0LA_0LA---}}
|-
|BLB(2,2)
|8
|8
|{{TM|1RB0RA_1LB1LA}}
|{{TM|1RB0RA_1LB1LA}}
|-
|-
|BLB(3)
|BLB(3,2)
|34
|34
|{{TM|1RB1LB_1LA1LC_1RC0LC}}
|{{TM|1RB1LB_1LA1LC_1RC0LC}}
Line 92: Line 154:
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|-
|-
|BLB(4)
|BLB(4,2)
|32,779,477
|32,779,477
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
|{{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)
|BLB(2,4)
Line 107: Line 177:
!Champion
!Champion
|-
|-
|BBr(2)
|BBr(2,2,1)
|4
|{{TM|0RB---_1LA---|halt}}
|-
|BBr(2,2)
|6
|6
|{{TM|0RB1RZ_1LA1RB|halt}}
|{{TM|0RB---_1LA1RB|halt}}
|-
|-
|BBr(3)
|BBr(3,2)
|17
|17
|{{TM|0RB1RZ_0LC1RA_1RB1LC|halt}}
|{{TM|0RB---_0LC1RA_1RB1LC|halt}}
|-
|-
|BBr(4)
|BBr(4,2)
|48
|48
|{{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ|halt}}
|{{TM|1RB0LD_0LC0RB_1LA1LD_1LC---|halt}}
|-
|-
|BBr(5)
|BBr(5,2)
|388
|388
|{{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA|halt}}
|{{TM|1RB0RD_1RC0RB_1RD---_1LE1LA_0LE0LA|halt}}
|-
|-
|BBr(6)
|BBr(6,2)
|537,556
|537,556
|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA|halt}}
|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA---_1RF1RA|halt}}
|-
|-
|BBr(7)
|BBr(7,2)
|<math>10^{19}</math>
|<math>10^{19}</math>
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ|halt}}
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB---|halt}}
|}
|}


== Lambda Calculus ==
=== Consecutive ones ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBn(2,2,1)
|2
|{{TM|1RB---_1LA---|halt}}
|-
|BBn(2,2)
|4
|{{TM|1RB1LB_1LA---|halt}}
|-
|BBn(2,3)
|5
|{{TM|1RB1LB_1RC1LC_1LA---|halt}}
|-
|BBn(3,2)
|6
|{{TM|1RB1LC_1RC---_1LA0LB|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}}
|}


=== SK Calculus ===
=== Semi infinite tape ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|BBt(2,2,1)
|1
|{{TM|1RB1LA_1LA---|halt}}
|-
|BBt(2,2)
|2
|{{TM|1RB1RB_1LA1LB|halt}}
|-
|BBt(3,2,1)
|4
|{{TM|0RB---_1LA1RC_1LB0LC|halt}}
|-
|BBt(3,2)
|6
|{{TM|0RB1RC_1LA1RB_1RB0LC|halt}}
|}
 
=== Turmite ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TT(2,2,1)
|3
|<code>1PB---_1TA---</code>
|-
|TT(2,2)
|6
|<code>1PB1PB_1TA---</code>
|}
 
== Lambda calculus ==
 
=== SK calculus ===
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 142: Line 289:
|SKBB(4)
|SKBB(4)
|4
|4
|SSSS
|<code>SSSS</code>
|-
|-
|SKBB(5)
|SKBB(5)
|6
|6
|SSS(SS)
|<code>SSS(SS)</code>
|-
|-
|SKBB(6)
|SKBB(6)
|8
|8
|SSS(SSS)
|<code>SSS(SSS)</code>
|-
|-
|SKBB(7)
|SKBB(7)
|10
|10
|SSS(SSSS)
|<code>SSS(SSSS)</code>
|-
|-
|SKBB(8)
|SKBB(8)
|23
|23
|SSS(S(SKS))S
|<code>SSS(S(SKS))S</code>
|}
 
=== BCKW calculus ===
{| 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>
|}
|}


Line 167: Line 345:
!Champion
!Champion
|-
|-
|BBdb(6)
|BBL(6)
|6
|6
|<code>\1 1 1 1 1 1</code>
|<code>\1 1 1 1 1 1</code>
|-
|-
|BBdb(7)
|BBL(7)
|15
|15
|<code>(\1 1) (\\2 (1 2))</code>
|<code>(\1 1) (\\2 (1 2))</code>
|-
|-
|BBdb(8)
|BBL(8)
|67
|67
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|<code>(\1 1) (\\2 (2 (1 2)))</code>
|-
|-
|BBdb(9)
|BBL(9)
|<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>
|-
|-
|BBdb(10)
|BBL(10)
|<math>10^{7 \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>
|-
|-
|BBdb(11)
|BBL(11)
|<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>
|-
|-
|BBdb(12)
|BBL(12)
|<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>
|-
|-
|BBdb(13)
|BBL(13)
|<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>
|-
|-
|BBdb(14)
|BBL(14)
|<math>f_{\omega+1}(10^{10^{65,536}})</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>
|}
|}


== Cyclic Tag ==
== Tag system ==
 
=== 2-tag system ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|TTBB(3)
|1
|<code>Δ: aa P: _</code>
|-
|TTBB(4)
|1
|<code>Δ: aaa P: _</code>
|-
|TTBB(5)
|2
|<code>Δ: aaaa P: _</code>
|-
|TTBB(6)
|2
|<code>Δ: aaaaa P: _</code>
|-
|TTBB(7)
|3
|<code>Δ: aaaaaa P: _</code>
|-
|TTBB(8)
|4
|<code>Δ: aaaa P: bb, _</code>
|-
|TTBB(9)
|5
|<code>Δ: aaaaa P: bb, _</code>
|-
|TTBB(10)
|6
|<code>Δ: aaaaaa P: bb, _</code>
|-
|TTBB(11)
|7
|<code>Δ: aaaaaaa P: bb, _</code>
|-
|TTBB(12)
|24
|<code>Δ: aaa P: bc, a, aaa</code>
|}
 
=== Cyclic tag ===
{| class="wikitable"
{| class="wikitable"
!Domain
!Domain
Line 211: Line 438:
|-
|-
|CTBB(2)
|CTBB(2)
|5
|1
|Δ: (()) P: ()() > _, () > ()()
|<code>Δ: 1 P: _</code>
|-
|-
|CTBB(3)
|CTBB(3)
|38
|2
|Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
|<code>Δ: 11 P: _</code>
|-
|-
|CTBB(4)
|CTBB(4)
|672
|4
|Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
|<code>Δ: 11 P: 0</code>
|-
|-
|CTBB(5)
|CTBB(5)
|<math>10 {\uparrow}^{2} 4 \,|\, 54</math>
|6
|Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
|<code>Δ: 111 P: 0</code>
|-
|-
|CTBB(6)
|CTBB(6)
|<math>10 {\uparrow}^{3} 129</math>
|9
|Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
|<code>Δ: 111 P: 00</code>
|-
|-
|CTBB(7)
|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 rewrite ===
{| 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>
|<math>10 {\uparrow}^{4} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 4</math>
|Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _
|<code>Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _</code>
|}
|}


Line 297: Line 591:
!Lower Bound
!Lower Bound
!Champion
!Champion
|-
|BFBB(4)
|4
|<code>++++</code>
|-
|BFBB(5)
|5
|<code>+++++</code>
|-
|-
|BFBB(6)
|BFBB(6)
Line 340: Line 626:
!Lower Bound
!Lower Bound
!Champion
!Champion
|-
|BLBB(6)
|6
|<code>>>>>>></code>
|-
|-
|BLBB(7)
|BLBB(7)
Line 350: Line 632:
|-
|-
|BLBB(8)
|BLBB(8)
|8
|9
|<code>>>>>>>>></code>
|<code>*>*[<<>]</code>
|-
|-
|BLBB(9)
|BLBB(9)
|9
|10
|<code>>>>>>>>>></code>
|<code>*>*[<<>]></code>
|-
|-
|BLBB(10)
|BLBB(10)
|11
|14
|<code>*>*>*>*[<]</code>
|<code>*>*>*[<<>]</code>
|-
|-
|BLBB(11)
|BLBB(11)
|12
|17
|<code>*>*>*>*[<]></code>
|<code>*>>>*[<<>*]</code>
|-
|-
|BLBB(12)
|BLBB(12)
|14
|21
|<code>*>*>*>*>*[<]</code>
|<code>*>>>>*[<<>*]</code>
|}
|}


Line 375: Line 657:
!Lower Bound
!Lower Bound
!Champion
!Champion
|-
|BCBB(4)
|4
|<code><nowiki>}}}}</nowiki></code>
|-
|BCBB(5)
|5
|<code><nowiki>}}}}}</nowiki></code>
|-
|BCBB(6)
|6
|<code><nowiki>}}}}}}</nowiki></code>
|-
|-
|BCBB(7)
|BCBB(7)
Line 418: Line 688:
!Lower Bound
!Lower Bound
!Champion
!Champion
|-
|BTBB(4)
|4
|<code>>>>></code>
|-
|BTBB(5)
|5
|<code>>>>>></code>
|-
|BTBB(6)
|6
|<code>>>>>>></code>
|-
|-
|BTBB(7)
|BTBB(7)
Line 454: Line 712:
|17
|17
|<code>>>>>>>>><[<]</code>
|<code>>>>>>>>><[<]</code>
|}
== Register machines ==
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|RBB(1)
|1
|<code>A- > H, 1</code>
|-
|RBB(2)
|3
|<code>A- > H, 2 / A+ > 1</code>
|-
|RBB(3)
|5
|<code>A+ > 2 / B- > H, 3 / B+ > 1</code>
|-
|RBB(4)
|8
|<code>B+ > 2 / B+ > 3 / A+ > 4 / B- > 3, H</code>
|-
|RBB(5)
|11
|<code>B+ > 2 / B+ > 3 / A+ > 4 / A+ > 5 / B- > 3, H</code>
|-
|RBB(6)
|15
|<code>B+ > 2 / B+ > 3 / B+ > 4 / A+ > 5 / A+ > 6 / B- > 4, H</code>
|}
|}

Latest revision as of 16:46, 8 December 2025

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.

Turing machines

Normal

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(3,3,1) 678 1RB1LB1LA_2RC2RB---_0LA1RC--- (bbch)
BB(2,4) 3,932,964 1RB2LA1RA1RA_1LB1LA3RB--- (bbch)
BB(5,2) 47,176,870 1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA (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

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

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

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

Domain Lower Bound Champion
BBt(2,2,1) 1 1RB1LA_1LA--- (bbch)
BBt(2,2) 2 1RB1RB_1LA1LB (bbch)
BBt(3,2,1) 4 0RB---_1LA1RC_1LB0LC (bbch)
BBt(3,2) 6 0RB1RC_1LA1RB_1RB0LC (bbch)

Turmite

Domain Lower Bound Champion
TT(2,2,1) 3 1PB---_1TA---
TT(2,2) 6 1PB1PB_1TA---

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(6) 6 \1 1 1 1 1 1
BBL(7) 15 (\1 1) (\\2 (1 2))
BBL(8) 67 (\1 1) (\\2 (2 (1 2)))
BBL(9) 7.625×1012 (\1 1 1) (\\2 (2 (2 1)))
BBL(10) 107.625×1012 (\1 1 1 1) (\\2 (2 (2 1)))
BBL(11) 10↑316 (\1 1 1) (\1 (\\2 (2 1)) 1)
BBL(12) 10↑310↑310↑26 (\1 1) (\1 (\1 (\\2 (2 1)) 2))
BBL(13) 10↑310↑310↑316 (\1 1 1 1 1) (\1 (\\2 (2 1)) 1)
BBL(14) fω+1(101019,727) (\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))

Tag system

2-tag system

Domain Lower Bound Champion
TTBB(3) 1 Δ: aa P: _
TTBB(4) 1 Δ: aaa P: _
TTBB(5) 2 Δ: aaaa P: _
TTBB(6) 2 Δ: aaaaa P: _
TTBB(7) 3 Δ: aaaaaa P: _
TTBB(8) 4 Δ: aaaa P: bb, _
TTBB(9) 5 Δ: aaaaa P: bb, _
TTBB(10) 6 Δ: aaaaaa P: bb, _
TTBB(11) 7 Δ: aaaaaaa P: bb, _
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]

Brainfuck

Brainfuck

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

Boolfuck

Domain Lower Bound Champion
BLBB(7) 7 >>>>>>>
BLBB(8) 9 *>*[<<>]
BLBB(9) 10 *>*[<<>]>
BLBB(10) 14 *>*>*[<<>]
BLBB(11) 17 *>>>*[<<>*]
BLBB(12) 21 *>>>>*[<<>*]

BitChanger

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

Bitter

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

Register machines

Domain Lower Bound Champion
RBB(1) 1 A- > H, 1
RBB(2) 3 A- > H, 2 / A+ > 1
RBB(3) 5 A+ > 2 / B- > H, 3 / B+ > 1
RBB(4) 8 B+ > 2 / B+ > 3 / A+ > 4 / B- > 3, H
RBB(5) 11 B+ > 2 / B+ > 3 / A+ > 4 / A+ > 5 / B- > 3, H
RBB(6) 15 B+ > 2 / B+ > 3 / B+ > 4 / A+ > 5 / A+ > 6 / B- > 4, H
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Azerty/Busy_Beaver_Functions&oldid=5447"