Maximum Consecutive Ones Function: Difference between revisions
(Add an early appearance of the num(5) champion →Champions) |
(→Champions: Added "halt" to bbch-links of halting TMs) |
||
| Line 11: | Line 11: | ||
!Source | !Source | ||
|- | |- | ||
| [[BB(1)]]|| 1 || {{TM|1RZ---}} || <math>0^\infty \; 1 \; \textrm{Z>} \; 0^\infty</math> | | [[BB(1)]]|| 1 || {{TM|1RZ---|halt}} || <math>0^\infty \; 1 \; \textrm{Z>} \; 0^\infty</math> | ||
|Ben-Amram, Julstrom and Zwick (1996) | |Ben-Amram, Julstrom and Zwick (1996) | ||
|- | |- | ||
|[[BB(2)]] | |[[BB(2)]] | ||
|4 | |4 | ||
|{{TM|1RB1LB_1LA1LZ}} | |{{TM|1RB1LB_1LA1LZ|halt}} | ||
|<math>0^\infty \; 1 \; \textrm{<Z} \; 1^3 \; 0^\infty</math> | |<math>0^\infty \; 1 \; \textrm{<Z} \; 1^3 \; 0^\infty</math> | ||
|Ben-Amram, Julstrom and Zwick (1996) | |Ben-Amram, Julstrom and Zwick (1996) | ||
| Line 22: | Line 22: | ||
|[[BB(3)]] | |[[BB(3)]] | ||
|6 | |6 | ||
|{{TM|1RB1LC_1RC1LZ_1LA0LB}} and 3 others | |{{TM|1RB1LC_1RC1LZ_1LA0LB|halt}} and 3 others | ||
|<math>0^\infty \; 1 \; \textrm{<Z} \; 1^5 \; 0^\infty</math> | |<math>0^\infty \; 1 \; \textrm{<Z} \; 1^5 \; 0^\infty</math> | ||
|Ben-Amram, Julstrom and Zwick (1996) | |Ben-Amram, Julstrom and Zwick (1996) | ||
| Line 28: | Line 28: | ||
|[[BB(4)]] | |[[BB(4)]] | ||
|12 | |12 | ||
|{{TM|1RB0LA_1RC1LB_1LB1RD_1RZ0RA}} | |{{TM|1RB0LA_1RC1LB_1LB1RD_1RZ0RA|halt}} | ||
|<math>0^\infty \; 1^{12} \; \textrm{Z>} \; 0^\infty</math> | |<math>0^\infty \; 1^{12} \; \textrm{Z>} \; 0^\infty</math> | ||
|Ben-Amram, Julstrom and Zwick (1996) | |Ben-Amram, Julstrom and Zwick (1996) | ||
| Line 34: | Line 34: | ||
|[[BB(5)]] | |[[BB(5)]] | ||
|165 | |165 | ||
|{{TM|1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB}} | |{{TM|1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB|halt}} | ||
|<math>0^\infty \; 1^{165} \; \textrm{Z>} \; 0^\infty</math> | |<math>0^\infty \; 1^{165} \; \textrm{Z>} \; 0^\infty</math> | ||
|[https://groups.google.com/g/busy-beaver-discuss/c/pvtXPmuMsAg/m/UP0xcmwoEAAJ Announcement] by Andrés Sancho in Feb 2025 | |[https://groups.google.com/g/busy-beaver-discuss/c/pvtXPmuMsAg/m/UP0xcmwoEAAJ Announcement] by Andrés Sancho in Feb 2025 | ||
| Line 40: | Line 40: | ||
Note: All TMs here are listed in [[TNF-1RB]] format with the exception that sometimes the halt transition is chosen to be <code>1LZ</code> when that leads to a "simpler" halting configuration. | Note: All TMs here are listed in [[TNF-1RB]] format with the exception that sometimes the halt transition is chosen to be <code>1LZ</code> when that leads to a "simpler" halting configuration. | ||
For BB(3), there are actually 4 champion machines that all leave exactly 6 1s: {{TM|1RB1RZ_0RC1RB_1LC1LA}}, {{TM|1RB1LC_1LA1RB_1LB1RZ}}, {{TM|1RB1RA_1LC1RZ_1RA1LB}}, {{TM|1RB1LC_1RC1RZ_1LA0LB}}. | For BB(3), there are actually 4 champion machines that all leave exactly 6 1s: {{TM|1RB1RZ_0RC1RB_1LC1LA|halt}}, {{TM|1RB1LC_1LA1RB_1LB1RZ|halt}}, {{TM|1RB1RA_1LC1RZ_1RA1LB|halt}}, {{TM|1RB1LC_1RC1RZ_1LA0LB|halt}}. | ||
The num(5) champion was found in 2009 by Joachim Hertel.<ref>J. Hertel, "[https://content.wolfram.com/sites/19/2009/11/Hertel.pdf Computing the Uncomputable Rado Sigma Function]". The Mathematica Journal vol. 11 (2009).</ref><sup>p. 282</sup> | The num(5) champion was found in 2009 by Joachim Hertel.<ref>J. Hertel, "[https://content.wolfram.com/sites/19/2009/11/Hertel.pdf Computing the Uncomputable Rado Sigma Function]". The Mathematica Journal vol. 11 (2009).</ref><sup>p. 282</sup> | ||
Latest revision as of 19:07, 16 August 2025
The Maximum Consecutive Ones function (named by Ben-Amram, Julstrom and Zwick)[1] is a Busy Beaver function which measures the maximum number of consecutive 1s left on the tape at halt across all n-state 2-symbol Turing machines which leave all their 1s consecutively. Unlike , this allows some amount of order over the "API" of these TMs, so that their output can be used as inputs to another TM in some deterministic fashion. Note however, that this definition does not stipulate where the TM head must be positioned relative to the sequence of consecutive ones, so it is not completely trivial to use these results as input to a second TM.
This function is only defined for 2-symbol TMs. It is not entirely clear how best to extend it to multi-symbol TMs. One option would be to keep the definition the same, so only TMs which halt with all 1s on the tape would qualify. Another would be to allow any symbols as long as all non-0 symbols were in one contiguous chunk on the tape.
Champions
| Domain | Champion TM | Halting Config | Source | |
|---|---|---|---|---|
| BB(1) | 1 | 1RZ--- (bbch) |
Ben-Amram, Julstrom and Zwick (1996) | |
| BB(2) | 4 | 1RB1LB_1LA1LZ (bbch)
|
Ben-Amram, Julstrom and Zwick (1996) | |
| BB(3) | 6 | 1RB1LC_1RC1LZ_1LA0LB (bbch) and 3 others
|
Ben-Amram, Julstrom and Zwick (1996) | |
| BB(4) | 12 | 1RB0LA_1RC1LB_1LB1RD_1RZ0RA (bbch)
|
Ben-Amram, Julstrom and Zwick (1996) | |
| BB(5) | 165 | 1RB1LA_1RC1LE_1RD1RE_0LA1RC_1RZ0LB (bbch)
|
Announcement by Andrés Sancho in Feb 2025 |
Note: All TMs here are listed in TNF-1RB format with the exception that sometimes the halt transition is chosen to be 1LZ when that leads to a "simpler" halting configuration.
For BB(3), there are actually 4 champion machines that all leave exactly 6 1s: 1RB1RZ_0RC1RB_1LC1LA (bbch), 1RB1LC_1LA1RB_1LB1RZ (bbch), 1RB1RA_1LC1RZ_1RA1LB (bbch), 1RB1LC_1RC1RZ_1LA0LB (bbch).
The num(5) champion was found in 2009 by Joachim Hertel.[2]p. 282
References
- ↑ Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). A note on busy beavers and other creatures. Mathematical Systems Theory 29 (4), July-August 1996, 375-386.
- ↑ J. Hertel, "Computing the Uncomputable Rado Sigma Function". The Mathematica Journal vol. 11 (2009).