Least Busy Beaver: Difference between revisions
Jump to navigation
Jump to search
(Created page with "The '''least busy beaver''' <math>BB^-(n, m)</math> problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) invented by racheline on 15 Feb 2025. == Definition == Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including one...") |
mNo edit summary |
||
| Line 4: | Line 4: | ||
Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then | Let <math>BB_{init}(n, m, T)</math> be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then | ||
<math>BB^-(n, m) = min_T BB_{init}(n, m, T)</math> | <math display="block">BB^-(n, m) = min_T BB_{init}(n, m, T)</math> | ||
In other words, the minimal value across all possible starting tapes. This minimum must exist because the values of <math>BB_{init}(n, m, T)</math> are all positive integers and thus well ordered. | |||
Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore, | Note that <math>BB_{init}(n, m, B) = BB(n, m)</math> where B is the blank (all-zeros) tape. Therefore, | ||
<math>BB^-(n, m) \le BB(n, m)</math> | <math display="block">BB^-(n, m) \le BB(n, m)</math> | ||
We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math> | We have not yet found an example where we can prove that <math>BB^-(n, m) \ne BB(n, m)</math> | ||
Revision as of 18:19, 16 February 2025
The least busy beaver problem is a variation of the busy beaver problem which considers TM behavior across all starting tapes (not just blank tapes like the traditional BB problem) invented by racheline on 15 Feb 2025.
Definition
Let be the longest runtime for all n-state m-symbol TMs which halt when started on tape configuration T (where T is allowed to be any infinite tape configuration, including ones with an infinite number of non-zero values). Then
In other words, the minimal value across all possible starting tapes. This minimum must exist because the values of are all positive integers and thus well ordered.
Note that where B is the blank (all-zeros) tape. Therefore,
We have not yet found an example where we can prove that
