Lazy Beaver: Difference between revisions
Jump to navigation
Jump to search
m →Computed Values: Reformat table |
m added context |
||
| (One intermediate revision by one other user not shown) | |||
| Line 2: | Line 2: | ||
LB(n, m) is the smallest k > 0 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. | ||
Unlike the variant that uses score, LB is computable. This is because the number of steps taken before halting is a syntactic property, so Rice's theorem does not apply. | |||
== Computed Values == | == Computed Values == | ||
| Line 55: | Line 57: | ||
[[category:Functions]] | [[category:Functions]] | ||
* https://oeis.org/A337805 | * https://oeis.org/A337805: LB(n, 2) | ||
Latest revision as of 04:06, 9 October 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.
Unlike the variant that uses score, LB is computable. This is because the number of steps taken before halting is a syntactic property, so Rice's theorem does not apply.
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)