Lazy Beaver: Difference between revisions
Jump to navigation
Jump to search
m (→Computed Values: Add missing value) |
m (Right align table.) |
||
| (2 intermediate revisions by 2 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;" | ||
|+ | |+ | ||
! | ! | ||
| Line 57: | Line 57: | ||
== See Also == | == See Also == | ||
[[category:Functions]] | |||
* https://oeis.org/A337805 | * https://oeis.org/A337805 | ||
Latest revision as of 19:12, 14 August 2025
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:
| States | ||||||
|---|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | ||
| Symbols | 2 | 7 | 22 | 72 | 427 | 8,407 |
| 3 | 23 | 351 | 189,270 | |||
| 4 | 93 | 242,789 | ||||
| 5 | 956 | |||||
| 6 | 33,851 | |||||