Maximum Consecutive Ones Function: Difference between revisions
Jump to navigation
Jump to search
(Add reference) |
(→Champions: Added "halt" to bbch-links of halting TMs) |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
The '''Maximum Consecutive Ones''' function (named <math>num(n)</math> by Ben-Amram)<ref>Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> 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 machine]]s which leave all their 1s consecutively. Unlike <math>\Sigma(n)</math>, 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. | The '''Maximum Consecutive Ones''' function (named <math>num(n)</math> by Ben-Amram, Julstrom and Zwick)<ref>Ben-Amram A.M., Julstrom B.A. and Zwick U. (1996). [http://dx.doi.org/10.1007/BF01192693 A note on busy beavers and other creatures]. ''Mathematical Systems Theory'' '''29''' (4), July-August 1996, 375-386.</ref> 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 machine]]s which leave all their 1s consecutively. Unlike <math>\Sigma(n)</math>, 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. | 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. | ||
| Line 9: | Line 9: | ||
|- | |- | ||
! Domain !! <math>num(n)</math> !! Champion TM !! Halting Config | ! Domain !! <math>num(n)</math> !! Champion TM !! Halting Config | ||
!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) | |||
|- | |- | ||
|[[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) | |||
|- | |- | ||
|[[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) | |||
|- | |- | ||
|[[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) | |||
|- | |- | ||
|[[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 | |||
|} | |} | ||
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> | |||
== References == | == References == | ||
<references /> | <references /> | ||
[[category:Functions]] | |||
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).