Main Page: Difference between revisions
Jacobzheng (talk | contribs) (Undo revision 2546 by Tianxinhuinb666 (talk)) Tag: Undo |
(Advertising TMBR on main page) |
||
| Line 80: | Line 80: | ||
default=(Article title) | default=(Article title) | ||
</inputbox> | </inputbox> | ||
== This Month in Beaver Research (TMBR) == | |||
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] (TMBR, pronounced "timber"), is a monthly summary of Busy Beaver research progress. Here are the last 3 entries: | |||
* [[TMBR: July 2025|TMBR July 2025]] | |||
==Notes== | ==Notes== | ||
<references /> | <references /> | ||
Revision as of 08:24, 4 August 2025
The Busy Beaver function BB (called S originally) was introduced by Tibor Radó in 1962 for 2-symbol Turing machines and later generalised to m-symbol Turing machines:[1][2]
| BB(n, m) = Maximum number of steps taken by a halting n-state, m-symbol Turing machine starting from a blank (all 0) tape |
The 2-symbol case BB(n, 2) is abbreviated as BB(n). The busy beaver function is not computable, but a few of its values are known:
| 2-state | 3-state | 4-state | 5-state | 6-state | 7-state | |
|---|---|---|---|---|---|---|
| 2-symbol | BB(2) = 6 | BB(3) = 21 | BB(4) = 107 | BB(5) = 47,176,870 | BB(6) > | BB(7) > |
| 3-symbol | BB(2,3) = 38 | BB(3,3) > | BB(4,3) > | |||
| 4-symbol | BB(2,4) = 3,932,964 | BB(3,4) > | ||||
| 5-symbol | BB(2,5) > | BB(3,5) > | ||||
| 6-symbol | BB(2,6) > |
In the above table, cells are highlighted in orange when there are known Cryptids (mathematically-hard machines) in that class, and cells are highlighted in light orange when the existence of a Cryptid is given by using a known one with less states or symbols.
About bbchallenge
bbchallenge is a massively collaborative research project whose general goal is to obtain more knowledge on the Busy Beaver function. In practice, it mainly consists in collaboratively building Deciders, programs that automatically prove that some Turing machines do not halt. Other efforts also include:
- Formalising results using theorem provers (such as Coq)
- Maintaining Holdouts lists for small busy beaver values
- Proving the behavior of Individual machines
- Finding Cryptids (mathematically-hard machines)
- Searching for new Champions
- Building Accelerated Simulators to simulate halting machines faster
- Writing papers and giving talks about busy beaver, see Papers & Talks
In June 2024, bbchallenge achieved a significant milestone by proving in Coq / Rocq that the 5th busy beaver value, BB(5), is equal to the lower bound found in 1989: 47,176,870.[4]
Contribute to this wiki
This wiki is collaborative, feel free to contribute by editing existing pages or creating new ones:
This Month in Beaver Research (TMBR)
This Month in Beaver Research (TMBR, pronounced "timber"), is a monthly summary of Busy Beaver research progress. Here are the last 3 entries:
Notes
- ↑ Rado, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x
- ↑ Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.
- ↑ P. Michel, "Historical survey of Busy Beavers".
- ↑ H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html