User:Azerty/Busy Beaver Functions: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
Azerty (talk | contribs)
65 edits
No edit summary
Azerty (talk | contribs)
65 edits
Added CTBB function.
Line 12: Line 12:
!Lower Bound
!Lower Bound
!Champion
!Champion
!Holdouts
|-
|-
|[[BB(2)]]
|[[BB(2)]]
|6
|6
|{{TM|1RB1LB_1LA1RZ|halt}}
|{{TM|1RB1LB_1LA1RZ|halt}}
|0
|-
|-
|[[BB(3)]]
|[[BB(3)]]
|21
|21
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|0
|-
|-
|[[BB(2,3)]]
|[[BB(2,3)]]
|38
|38
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|0
|-
|-
|[[BB(4)]]
|[[BB(4)]]
|107
|107
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|0
|-
|-
|[[BB(2,4)]]
|[[BB(2,4)]]
|3,932,964
|3,932,964
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|0
|-
|-
|[[BB(5)]]
|[[BB(5)]]
|47,176,870
|47,176,870
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|0
|-
|-
|[[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_1RZ1LB1LC|halt}}
|6
|-
|-
|[[BB(2,5)]]
|[[BB(2,5)]]
|<math>10^{10^{10^{3\,314\,360}}}</math>
|<math>10^{10^{10^{3\,314\,360}}}</math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|75
|-
|-
|[[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_2LA2RA4RB1RZ3LB2LA|halt}}
|870,085
|-
|[[BB(2,7)]]
|<math>10 {\uparrow}^{2} 10 {\uparrow}^{2} 10^{10^{115}}</math>
|{{TM|1RB3RB5RA1LB5LA2LB---_2LA2RA4RB1RZ3LB2LA---|halt}}
|
|-
|-
|[[BB(6)]]
|[[BB(6)]]
|<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_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|1,416
|-
|-
|[[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_1RZ1LA1LD_0RB2RA2RD|halt}}
|9,401,447
|-
|-
|[[BB(7)]]
|[[BB(7)]]
|<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_1RZ0LC_1RG1LD_0RG0RF|halt}}
|20,405,295
|-
|-
|[[BB(3,4)]]
|[[BB(3,4)]]
|<math>10 \uparrow^{15} 4</math>
|<math>10 \uparrow^{15} 4</math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|15,136,283
|-
|-
|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_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|-
|[[BB(2,7)]]
|
|
|
|}
|}
Line 95: Line 79:
!Lower Bound
!Lower Bound
!Champion
!Champion
!Holdouts
|-
|-
|BLB(2)
|BLB(2)
|8
|8
|{{TM|1RB0RA_1LB1LA}}
|{{TM|1RB0RA_1LB1LA}}
|
|-
|-
|BLB(3)
|BLB(3)
|34
|34
|{{TM|1RB1LB_1LA1LC_1RC0LC}}
|{{TM|1RB1LB_1LA1LC_1RC0LC}}
|
|-
|-
|BLB(2,3)
|BLB(2,3)
|77
|77
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|{{TM|1RB2LA0RB_1LA0LB1RA}}
|
|-
|-
|BLB(4)
|BLB(4)
|32,779,477
|32,779,477
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}}
|
|-
|-
|BLB(2,4)
|BLB(2,4)
|<math>1.367 \times 10^{12}</math>
|<math>1.367 \times 10^{12}</math>
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}}
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}}
|
|}
|}


Line 128: Line 106:
!Lower Bound
!Lower Bound
!Champion
!Champion
!Holdouts
|-
|-
|BBR(2)
|BBr(2)
|6
|6
|{{TM|0RB1RZ_1LA1RB|halt}}
|{{TM|0RB1RZ_1LA1RB|halt}}
|0
|-
|-
|BBR(3)
|BBr(3)
|17
|17
|{{TM|0RB1RZ_0LC1RA_1RB1LC|halt}}
|{{TM|0RB1RZ_0LC1RA_1RB1LC|halt}}
|0
|-
|-
|BBR(4)
|BBr(4)
|48
|48
|{{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ|halt}}
|{{TM|1RB0LD_0LC0RB_1LA1LD_1LC1RZ|halt}}
|0
|-
|-
|BBR(5)
|BBr(5)
|388
|388
|{{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA|halt}}
|{{TM|1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA|halt}}
|0
|-
|-
|BBR(6)
|BBr(6)
|537,556
|537,556
|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA|halt}}
|{{TM|1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA|halt}}
|
|-
|-
|BBR(7)
|BBr(7)
|<math>10^{19}</math>
|<math>10^{19}</math>
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ|halt}}
|{{TM|1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ|halt}}
|
|}
|}


== Turing Machines ==
== Lambda Calculus ==
 
=== SK Calculus ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|SKBB(1)
|1
|S
|-
|SKBB(2)
|2
|SS
|-
|SKBB(3)
|3
|SSS
|-
|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
|}
 
== Cyclic Tag ==
 
=== Cyclic Tag ===
{| class="wikitable"
!Domain
!Lower Bound
!Champion
|-
|CTBB(2)
|5
|Δ: (()) P: ()() > _, () > ()()
|-
|CTBB(3)
|38
|Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
|-
|CTBB(4)
|672
|Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
|-
|CTBB(5)
|<math>10 {\uparrow}^{2} 4 | 182</math>
|Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
|-
|CTBB(6)
|<math>10 {\uparrow}^{3} 129</math>
|Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
|-
|CTBB(7)
|<math>10 {\uparrow}^{4} 10 {\uparrow}^{2} 10 {\uparrow}^{2} 4</math>
|Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _
|}

Revision as of 14:10, 4 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.

I will add more functions soon.

Turing Machines

Normal

Domain Lower Bound Champion
BB(2) 6 1RB1LB_1LA1RZ (bbch)
BB(3) 21 1RB1RZ_1LB0RC_1LC1LA (bbch)
BB(2,3) 38 1RB2LB1RZ_2LA2RB1LB (bbch)
BB(4) 107 1RB1LB_1LA0LC_1RZ1LD_1RD0RA (bbch)
BB(2,4) 3,932,964 1RB2LA1RA1RA_1LB1LA3RB1RZ (bbch)
BB(5) 47,176,870 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch)
BB(3,3) 1.191×1017 0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC (bbch)
BB(2,5) 1010103314360 1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ (bbch)
BB(2,6) 10↑210↑21010115 1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch)
BB(6) 10↑210↑210↑28 1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch)
BB(4,3) 10↑310↑310↑31028 1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch)
BB(7) 10↑1110↑104 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch)
BB(3,4) 10↑154 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(3,5) fω(10↑154) 1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC (bbch)
BB(2,7)

Blanking

Domain Lower Bound Champion
BLB(2) 8 1RB0RA_1LB1LA (bbch)
BLB(3) 34 1RB1LB_1LA1LC_1RC0LC (bbch)
BLB(2,3) 77 1RB2LA0RB_1LA0LB1RA (bbch)
BLB(4) 32,779,477 1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch)
BLB(2,4) 1.367×1012 1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)

Reversible

Domain Lower Bound Champion
BBr(2) 6 0RB1RZ_1LA1RB (bbch)
BBr(3) 17 0RB1RZ_0LC1RA_1RB1LC (bbch)
BBr(4) 48 1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch)
BBr(5) 388 1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA (bbch)
BBr(6) 537,556 1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA (bbch)
BBr(7) 1019 1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ (bbch)

Lambda Calculus

SK Calculus

Domain Lower Bound Champion
SKBB(1) 1 S
SKBB(2) 2 SS
SKBB(3) 3 SSS
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

Cyclic Tag

Cyclic Tag

Domain Lower Bound Champion
CTBB(2) 5 Δ: (()) P: ()() > _, () > ()()
CTBB(3) 38 Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
CTBB(4) 672 Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
CTBB(5) 10↑24|182 Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
CTBB(6) 10↑3129 Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
CTBB(7) 10↑410↑210↑24 Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:Azerty/Busy_Beaver_Functions&oldid=5289"