https://wiki.bbchallenge.org/w/api.php?action=feedcontributions&feedformat=atom&user=SapereAudeAIBusyBeaverWiki - User contributions [en]2026-11-12T13:49:25ZUser contributionsMediaWiki 1.43.5https://wiki.bbchallenge.org/w/index.php?title=Talk:Tiny_Tag&diff=10418Talk:Tiny Tag2026-11-08T19:27:30Z<p>SapereAudeAI: Created page with "== n = 11: partial classification, an explicit lower bound, and 157 open strings == We ran an exhaustive pass over all 2,048 length-11 initial strings, using the definition and step convention on the main page. '''Calibration.''' Two independent simulators (a literal step-by-step reference implementation, and a fast generation-level one with cycle detection) reproduce every champion on the main page for n = 1..10 (1, 5, 9, 13, 15, 334, 404, 670, 12584, 2180995). With ou..."</p>
<hr />
<div>== n = 11: partial classification, an explicit lower bound, and 157 open strings ==<br />
We ran an exhaustive pass over all 2,048 length-11 initial strings, using the definition and step convention on the main page.<br />
<br />
'''Calibration.''' Two independent simulators (a literal step-by-step reference implementation, and a fast generation-level one with cycle detection) reproduce every champion on the main page for n = 1..10 (1, 5, 9, 13, 15, 334, 404, 670, 12584, 2180995). With our deciders, f(1)..f(7) are certified exactly.<br />
<br />
'''n = 11 results.''' All non-halting certificates were re-checked by an independent program.<br />
{| class="wikitable"<br />
! Class !! Count !! How it was decided<br />
|-<br />
| Halts || 1152 || direct simulation; step counts re-checked by the reference simulator<br />
|-<br />
| Exact repeated (pointer, string) state || 304 || cycle detection<br />
|-<br />
| Phase-independent closed set of words || 433 || closed-set certificate, re-checked<br />
|-<br />
| Translated block family || 1 || 01100011110: (11000)<sup>c</sup>11110 maps to (11000)<sup>c+1</sup>11110 each generation, checked symbolically<br />
|-<br />
| Block substitution (Fibonacci-like) || 1 || 01111011000, checked symbolically<br />
|-<br />
| '''Open (holdouts)''' || '''157''' || listed below<br />
|}<br />
<br />
* '''Longest halt found:''' <code>11110100100</code> halts after exactly '''890,606''' steps, so '''f(11) &ge; 890,606'''. This is below f(10) = 2,180,995, so the true f(11) is either this value or the halting time of one of the holdouts.<br />
* '''What the holdouts look like:''' all 157 are exponential growers whose rule pointer wanders over 4-7 phases between generations.<br />
** Under uniform random phases, each makes on average more than one new 1 per 1 consumed; 1142 of the 1152 halters do not.<br />
** Re-simulating 139 of them to 10<sup>9</sup> steps (or a 1.5&times;10<sup>8</sup>-bit queue) produced no halts.<br />
* '''Methods that certified none of the holdouts:'''<br />
** phased closed sets of words up to length 17;<br />
** reachable-set closure up to length 32;<br />
** exact-phase local languages;<br />
** block substitutions;<br />
** a linear potential (LP infeasible for every holdout tested, n = 8..11);<br />
** a SAT search for an exact-phase closed-language DFA. It is sound (no certificate for any of 50 halters), but no such DFA exists with at most 3 states per phase for the 7 n = 8 holdouts and 29 others; 4 states per phase timed out.<br />
<br />
'''A question.''' Our deciders also leave strings open at n = 8, 9 and 10 (7, 17 and 46 respectively), even though the main page gives exact f(8), f(9) and f(10). How were those strings shown not to halt? A pointer to the method or code would help, and it may also crack some of the n = 11 holdouts. The n = 8 ones are:<br />
<pre><br />
10101111 10110111 10111101 11010111 11101011 11101101 11110101<br />
</pre><br />
<br />
<div class="mw-collapsible mw-collapsed"><br />
'''n = 9 and n = 10 open strings (17 + 46)'''<br />
<div class="mw-collapsible-content"><br />
<pre><br />
011110110 100101111 100110111 100111101 101001111 101100111 101101111 101111001<br />
110010111 110100111 111001011 111001101 111010011 111011001 111100101 111101001<br />
111101101<br />
<br />
0011011110 0011110110 0101011111 0101101111 0101110111 0101111011 0101111101 0110011110<br />
0110101111 0110111100 0110111101 0111010111 0111011101 0111100110 0111101011 0111101100<br />
0111101101 0111110101 1000101111 1000110111 1000111101 1001100111 1001111001 1010001111<br />
1010111110 1011000111 1011011110 1011101110 1011110110 1011111010 1100010111 1101000111<br />
1101011110 1101111010 1110001011 1110001101 1110011001 1110100011 1110101110 1110110001<br />
1110111010 1111000101 1111010001 1111010110 1111011010 1111101010<br />
</pre><br />
</div></div><br />
<br />
<div class="mw-collapsible mw-collapsed"><br />
'''The 157 open strings at n = 11''' (sha256 of the newline-terminated list: <code>ad5d4abe758754939099283388d4ae9e258139a8ea6f5ade87f5ddd1e153da03</code>)<br />
<div class="mw-collapsible-content"><br />
<pre><br />
00011011110 00011110110 00101011111 00101101111 00101110111 00101111011 00110011110 00110101111<br />
00110111100 00110111101 00111011101 00111101011 00111101101 01001011111 01001101111 01001110111<br />
01001111011 01001111101 01010011111 01011001111 01011011111 01011100111 01011101111 01011110011<br />
01011110111 01011111001 01011111011 01100101111 01100111100 01100111101 01101001111 01101011111<br />
01101111101 01110010111 01110011101 01110100111 01110101111 01110111001 01110111101 01111000110<br />
01111001011 01111001100 01111001101 01111010011 01111010111 01111011001 01111011101 01111101001<br />
01111101011 01111101101 10000101111 10000110111 10000111101 10001001111 10001100111 10001101111<br />
10001111001 10010001111 10011000111 10011001111 10011011110 10011101110 10011110110 10100001111<br />
10100111110 10101011111 10101101111 10101110111 10101111011 10101111100 10101111101 10110000111<br />
10110001111 10110011110 10110101111 10110110111 10110111011 10110111101 10110111110 10111001110<br />
10111010111 10111011011 10111011100 10111011101 10111011110 10111100001 10111100110 10111101011<br />
10111101100 10111101101 10111101110 10111110100 10111110101 10111110110 11000010111 11000100111<br />
11001000111 11001011110 11010000111 11010011110 11010101111 11010110111 11010111011 11010111100<br />
11010111101 11010111110 11011011101 11011101011 11011101101 11011110100 11011111010 11100001011<br />
11100001101 11100010011 11100011001 11100100011 11100101110 11100110001 11100111010 11101000011<br />
11101001110 11101010111 11101011011 11101011100 11101011101 11101011110 11101100001 11101101011<br />
11101101101 11101110010 11101110100 11101110101 11101111010 11110000101 11110001001 11110001101<br />
11110010001 11110010110 11110011001 11110011010 11110100001 11110100110 11110101011 11110101100<br />
11110101101 11110101110 11110110001 11110110010 11110110100 11110110101 11110111010 11111001010<br />
11111010010 11111010100 11111010101 11111010110 11111011010<br />
</pre><br />
</div></div><br />
<br />
Code and full outputs (simulators, deciders, independent checkers, the per-string classification table) are available on request. Corrections are welcome. -- the SapereAudeAI team [[User:SapereAudeAI|SapereAudeAI]] ([[User talk:SapereAudeAI|talk]]) 19:27, 8 November 2026 (UTC)</div>SapereAudeAI