Lazy Beaver: Difference between revisions
Jump to navigation
Jump to search
m →Computed Values: Add missing value |
m →See Also: Note what OEIS seq is for. |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
The '''Lazy Beaver''' function is a computable variation of the Busy Beaver function defined by Scott Aaronson in his 2020 review. | The '''Lazy Beaver''' function is a computable variation of the Busy Beaver function defined by Scott Aaronson in his 2020 review. | ||
LB(n, m) is the smallest k such that no n-state, m-symbol [[Turing machine]] halts in exactly k steps. | LB(n, m) is the smallest k > 0 such that no n-state, m-symbol [[Turing machine]] halts in exactly k steps. | ||
== Computed Values == | == Computed Values == | ||
Values found by Terry and [[User:Sligocki|Shawn Ligocki]] in 2021: | Values found by Terry and [[User:Sligocki|Shawn Ligocki]] in 2021: | ||
{| class="wikitable" | {| class="wikitable" style="text-align: right;" | ||
|+LB(n, m) | |||
|- | |- | ||
! | ! | ||
!2-state | |||
!2 | !3-state | ||
!3 | !4-state | ||
!4 | !5-state | ||
!5 | !6-state | ||
!6 | |||
|- | |- | ||
!2-symbol | |||
|7 | |7 | ||
|22 | |22 | ||
| Line 27: | Line 22: | ||
|8,407 | |8,407 | ||
|- | |- | ||
!3-symbol | |||
|23 | |23 | ||
|351 | |351 | ||
| Line 34: | Line 29: | ||
| | | | ||
|- | |- | ||
!4-symbol | |||
|93 | |93 | ||
|242,789 | |242,789 | ||
| Line 41: | Line 36: | ||
| | | | ||
|- | |- | ||
!5-symbol | |||
|956 | |956 | ||
| | | | ||
| Line 48: | Line 43: | ||
| | | | ||
|- | |- | ||
!6-symbol | |||
|33,851 | |33,851 | ||
| | | | ||
| Line 58: | Line 53: | ||
== See Also == | == See Also == | ||
* https://oeis.org/A337805 | [[category:Functions]] | ||
* https://oeis.org/A337805: LB(n, 2) | |||
Latest revision as of 05:15, 21 June 2026
The Lazy Beaver function is a computable variation of the Busy Beaver function defined by Scott Aaronson in his 2020 review.
LB(n, m) is the smallest k > 0 such that no n-state, m-symbol Turing machine halts in exactly k steps.
Computed Values
Values found by Terry and Shawn Ligocki in 2021:
| 2-state | 3-state | 4-state | 5-state | 6-state | |
|---|---|---|---|---|---|
| 2-symbol | 7 | 22 | 72 | 427 | 8,407 |
| 3-symbol | 23 | 351 | 189,270 | ||
| 4-symbol | 93 | 242,789 | |||
| 5-symbol | 956 | ||||
| 6-symbol | 33,851 |
See Also
- https://oeis.org/A337805: LB(n, 2)