Blanking Busy Beaver Function: Difference between revisions
Jump to navigation
Jump to search
Made a general note about 1-state BLB champions being nonexistent |
m →Instruction-limited Blanking Busy Beaver (BLBi(n)): to tape --> on the tape |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
The '''Blanking Busy Beaver Function''' (BLB(n,m)) is a [[Busy Beaver Functions|Busy Beaver Function]] which measures the largest amount of steps done by any [[Turing machine]] with n states and m symbols before blanking the tape. Blanking Busy Beaver machines are allowed to be halting or non-halting. As machines with just a single state cannot blank the tape, BLB(1,m) is nonexistent for any amount of symbols m. | The '''Blanking Busy Beaver Function''' (BLB(n,m)) is a [[Busy Beaver Functions|Busy Beaver Function]] which measures the largest amount of steps done by any [[Turing machine]] with n states and m symbols before blanking the tape. Blanking Busy Beaver machines are allowed to be halting or non-halting. As machines with just a single state cannot blank the tape, BLB(1,m) is nonexistent for any amount of symbols m. Similarly, BLB(n,1) is nonexistent for any amount of states n, as the tape of [[BB(n,1)|1-symbol machines]] is always blank. | ||
==Champions== | == Champions == | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
| Line 9: | Line 9: | ||
|- | |- | ||
|BLB(2) | |BLB(2) | ||
| | |≥ 8<ref name=":3">Nick Drozd. "[https://nickdrozd.github.io/2021/02/14/blanking-beavers.html Blanking Beavers]". Accessed 15 August 2025.</ref> | ||
|{{TM|1RB0RA_1LB1LA}} | |{{TM|1RB0RA_1LB1LA}} | ||
|- | |- | ||
|BLB(3) | |BLB(3) | ||
| | |≥ 34<ref name=":4">Nick Drozd. "[https://nickdrozd.github.io/2022/02/11/latest-beeping-busy-beaver-results.html Latest Beeping Busy Beaver Results]". Accessed 15 August 2025.</ref> | ||
|{{TM|1RB1LB_1LA1LC_1RC0LC}} | |{{TM|1RB1LB_1LA1LC_1RC0LC}} | ||
|- | |- | ||
|BLB(4) | |BLB(4) | ||
| | |≥ 32,779,477 | ||
|{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} | |{{TM|1RB1LD_1RC1RB_1LC1LA_0RC0RD}} | ||
|- | |||
|BLB(5) | |||
|≥ 32,810,047<ref>Comment #71 "https://scottaaronson.blog/?p=5661". Accessed 26 September 2025.</ref> | |||
|{{TM|1RB1LC_1RD0LE_0RD0RC_1LD1LA_1RB1RE}} | |||
|- | |||
|BLB(6) | |||
|≥ 65,538,549<ref>Comment #62 "https://scottaaronson.blog/?p=5661". Accessed 26 September 2025.</ref> | |||
|{{TM|1RB1LE_1RD1RB_0RD0RE_1LD1LA_0RF1RF_0LC1LC}} | |||
|} | |} | ||
{| class="wikitable" | {| class="wikitable" | ||
| Line 27: | Line 35: | ||
|- | |- | ||
|BLB(2,3) | |BLB(2,3) | ||
| | |≥ 77<ref name=":4" /> | ||
|{{TM|1RB2LA0RB_1LA0LB1RA}} | |{{TM|1RB2LA0RB_1LA0LB1RA}} | ||
|} | |} | ||
| Line 37: | Line 45: | ||
|- | |- | ||
|BLB(2,4) | |BLB(2,4) | ||
| | |≥ 1,367,361,263,049<ref name=":4" /> | ||
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}} | |||
|} | |||
== [[Instruction-Limited Busy Beaver|Instruction-limited]] Blanking Busy Beaver (BLBi(n)) == | |||
BLBi(n) is the largest amount of steps taken by an n-instruction Turing machine when blanking the tape for the first time after having written a non-blank symbol on the tape. | |||
=== Champions === | |||
Note that BLBi(1) and BLBi(2) are nonexistent as Turing machines with one or two instructions cannot blank the tape. | |||
{| class="wikitable" | |||
|+ | |||
!Instructions | |||
!Steps | |||
!Champions | |||
|- | |||
|BLBi(3) | |||
|4 | |||
|? | |||
|- | |||
|BLBi(4) | |||
|12 | |||
|? | |||
|- | |||
|BLBi(5) | |||
|30 | |||
|? | |||
|- | |||
|BLBi(6) | |||
|77 | |||
|{{TM|1RB2LA0RB_1LA0LB1RA}} | |||
|- | |||
|BLBi(7) | |||
|808 | |||
|? | |||
|- | |||
|BLBi(8) | |||
|≥ 1,367,361,263,049 | |||
|{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}} | |{{TM|1RB2RA1RA2RB_2LB3LA0RB0RA}} | ||
|} | |} | ||
Latest revision as of 12:58, 26 December 2025
The Blanking Busy Beaver Function (BLB(n,m)) is a Busy Beaver Function which measures the largest amount of steps done by any Turing machine with n states and m symbols before blanking the tape. Blanking Busy Beaver machines are allowed to be halting or non-halting. As machines with just a single state cannot blank the tape, BLB(1,m) is nonexistent for any amount of symbols m. Similarly, BLB(n,1) is nonexistent for any amount of states n, as the tape of 1-symbol machines is always blank.
Champions
| 2 Symbols: | Steps | Champions |
|---|---|---|
| BLB(2) | ≥ 8[1] | 1RB0RA_1LB1LA (bbch)
|
| BLB(3) | ≥ 34[2] | 1RB1LB_1LA1LC_1RC0LC (bbch)
|
| BLB(4) | ≥ 32,779,477 | 1RB1LD_1RC1RB_1LC1LA_0RC0RD (bbch)
|
| BLB(5) | ≥ 32,810,047[3] | 1RB1LC_1RD0LE_0RD0RC_1LD1LA_1RB1RE (bbch)
|
| BLB(6) | ≥ 65,538,549[4] | 1RB1LE_1RD1RB_0RD0RE_1LD1LA_0RF1RF_0LC1LC (bbch)
|
| 3 Symbols: | Steps | Champions |
|---|---|---|
| BLB(2,3) | ≥ 77[2] | 1RB2LA0RB_1LA0LB1RA (bbch)
|
| 4 Symbols: | Steps | Champions |
|---|---|---|
| BLB(2,4) | ≥ 1,367,361,263,049[2] | 1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)
|
Instruction-limited Blanking Busy Beaver (BLBi(n))
BLBi(n) is the largest amount of steps taken by an n-instruction Turing machine when blanking the tape for the first time after having written a non-blank symbol on the tape.
Champions
Note that BLBi(1) and BLBi(2) are nonexistent as Turing machines with one or two instructions cannot blank the tape.
| Instructions | Steps | Champions |
|---|---|---|
| BLBi(3) | 4 | ? |
| BLBi(4) | 12 | ? |
| BLBi(5) | 30 | ? |
| BLBi(6) | 77 | 1RB2LA0RB_1LA0LB1RA (bbch)
|
| BLBi(7) | 808 | ? |
| BLBi(8) | ≥ 1,367,361,263,049 | 1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)
|
References
- ↑ Nick Drozd. "Blanking Beavers". Accessed 15 August 2025.
- ↑ 2.0 2.1 2.2 Nick Drozd. "Latest Beeping Busy Beaver Results". Accessed 15 August 2025.
- ↑ Comment #71 "https://scottaaronson.blog/?p=5661". Accessed 26 September 2025.
- ↑ Comment #62 "https://scottaaronson.blog/?p=5661". Accessed 26 September 2025.