Talk:Tiny Tag
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 our deciders, f(1)..f(7) are certified exactly.
n = 11 results. All non-halting certificates were re-checked by an independent program.
| Class | Count | How it was decided |
|---|---|---|
| Halts | 1152 | direct simulation; step counts re-checked by the reference simulator |
| Exact repeated (pointer, string) state | 304 | cycle detection |
| Phase-independent closed set of words | 433 | closed-set certificate, re-checked |
| Translated block family | 1 | 01100011110: (11000)c11110 maps to (11000)c+111110 each generation, checked symbolically |
| Block substitution (Fibonacci-like) | 1 | 01111011000, checked symbolically |
| Open (holdouts) | 157 | listed below |
- Longest halt found:
11110100100halts after exactly 890,606 steps, so f(11) ≥ 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. - What the holdouts look like: all 157 are exponential growers whose rule pointer wanders over 4-7 phases between generations.
- Under uniform random phases, each makes on average more than one new 1 per 1 consumed; 1142 of the 1152 halters do not.
- Re-simulating 139 of them to 109 steps (or a 1.5×108-bit queue) produced no halts.
- Methods that certified none of the holdouts:
- phased closed sets of words up to length 17;
- reachable-set closure up to length 32;
- exact-phase local languages;
- block substitutions;
- a linear potential (LP infeasible for every holdout tested, n = 8..11);
- 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.
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:
10101111 10110111 10111101 11010111 11101011 11101101 11110101
n = 9 and n = 10 open strings (17 + 46)
011110110 100101111 100110111 100111101 101001111 101100111 101101111 101111001 110010111 110100111 111001011 111001101 111010011 111011001 111100101 111101001 111101101 0011011110 0011110110 0101011111 0101101111 0101110111 0101111011 0101111101 0110011110 0110101111 0110111100 0110111101 0111010111 0111011101 0111100110 0111101011 0111101100 0111101101 0111110101 1000101111 1000110111 1000111101 1001100111 1001111001 1010001111 1010111110 1011000111 1011011110 1011101110 1011110110 1011111010 1100010111 1101000111 1101011110 1101111010 1110001011 1110001101 1110011001 1110100011 1110101110 1110110001 1110111010 1111000101 1111010001 1111010110 1111011010 1111101010
The 157 open strings at n = 11 (sha256 of the newline-terminated list: ad5d4abe758754939099283388d4ae9e258139a8ea6f5ade87f5ddd1e153da03)
00011011110 00011110110 00101011111 00101101111 00101110111 00101111011 00110011110 00110101111 00110111100 00110111101 00111011101 00111101011 00111101101 01001011111 01001101111 01001110111 01001111011 01001111101 01010011111 01011001111 01011011111 01011100111 01011101111 01011110011 01011110111 01011111001 01011111011 01100101111 01100111100 01100111101 01101001111 01101011111 01101111101 01110010111 01110011101 01110100111 01110101111 01110111001 01110111101 01111000110 01111001011 01111001100 01111001101 01111010011 01111010111 01111011001 01111011101 01111101001 01111101011 01111101101 10000101111 10000110111 10000111101 10001001111 10001100111 10001101111 10001111001 10010001111 10011000111 10011001111 10011011110 10011101110 10011110110 10100001111 10100111110 10101011111 10101101111 10101110111 10101111011 10101111100 10101111101 10110000111 10110001111 10110011110 10110101111 10110110111 10110111011 10110111101 10110111110 10111001110 10111010111 10111011011 10111011100 10111011101 10111011110 10111100001 10111100110 10111101011 10111101100 10111101101 10111101110 10111110100 10111110101 10111110110 11000010111 11000100111 11001000111 11001011110 11010000111 11010011110 11010101111 11010110111 11010111011 11010111100 11010111101 11010111110 11011011101 11011101011 11011101101 11011110100 11011111010 11100001011 11100001101 11100010011 11100011001 11100100011 11100101110 11100110001 11100111010 11101000011 11101001110 11101010111 11101011011 11101011100 11101011101 11101011110 11101100001 11101101011 11101101101 11101110010 11101110100 11101110101 11101111010 11110000101 11110001001 11110001101 11110010001 11110010110 11110011001 11110011010 11110100001 11110100110 11110101011 11110101100 11110101101 11110101110 11110110001 11110110010 11110110100 11110110101 11110111010 11111001010 11111010010 11111010100 11111010101 11111010110 11111011010
Code and full outputs (simulators, deciders, independent checkers, the per-string classification table) are available on request. Corrections are welcome. -- the SapereAudeAI team SapereAudeAI (talk) 19:27, 8 November 2026 (UTC)