bbchallenge - #forum-individual-machines - 1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD

This machine has a relatively low Brick's heuristic of 0.2193. mxdys classified it under "quadratic mess" in his classified2.txt. Wiki user Polygon has analyzed it: [link 1](https://wiki.bbchallenge.org/wiki/1RB1LE_1LB1LC_1RD0LE_---0RB_1RF1LA_0RA0RD), [link 2](https://wiki.bbchallenge.org/wiki/User:Polygon/Page_for_analyses). I arrived at the following set of rules. They ended up being quite similar to the ones found by Polygon, although I did my analysis independently. Let the notation "`a ... b [m] c ... d`" mean `0^inf 1^a 0 ... 0 1^b 0 1^m 0B> 0 1^c 0 ... 0 1^d 0^inf`. (So basically a series of numbers in unary.) Also let "L" denote the `0^inf` on the left side. Then we have the following rules: ``` a. L 1 [0] c ... -> L [c+4] ... b. L 2 [0] c ... -> L 2 [c+2] ... c. L 3 [0] c ... -> ***HALT*** d. L 4 [0] c ... -> L [c+8] ... e. L 2k+5 [0] c ... -> L 2 [2k+1] c+4 ... f. ... a 2k+6 [0] c ... -> ... a+1 [2k+2] c+4 ... g. ... a [1] c ... -> ... [a+c+3] ... h. ... a [4k+2] b ... -> ... a+k+2 [b+3k+1] ... i. L [3] c ... -> ***HALT*** j. L 2 [2k+3] b ... -> L [b+6k+11] ... k. L 2k_0+3 [2k_n+3] c ... -> L 2 [2k_0+1] 2k_n+1 c+3 ... l. L 2k_0+4 [2k_n+3] c ... -> L 1 [2k_0+2] 2k_n+1 c+3 ... m. ... a [4k+4] b ... -> ... a+k+1 [0] b+3k+3 n. L [2k+5] c ... -> L 2 [2k+1] c+3 ... ``` Here, `a,b,c,k >= 0`. Though we can write rules for lists of arbitrarily many unary numbers, in actual simulations starting from `[m]` for `m = 2, 3, 4, ...`, I only see up to four numbers at a time.

The forward simulation of this TM reaches `[2]` after 8 base steps. And then, ``` [2] -> 2 [1] -> [5] -> 2 [1] 3 -> [8] -> 2 [0] 6 -> 2 [8] -> 4 [0] 6 -> [14] -> 3 [2] 9 -> 5 [10] -> 7 [2] 6 -> 9 [7] -> 2 [7] 5 3 -> [28] 3 -> 7 [0] 24 -> 2 [3] 28 -> [39] -> 2 [35] 3 -> [110] -> 29 [82] -> 51 [61] -> 2 [49] 59 3 -> [208] 3 -> 52 [0] 159 -> 1 [48] 163 -> 13 [0] 199 -> 2 [9] 203 -> [232] -> 58 [0] 174 -> ... ``` After 10^7 rule steps, the TM has reached a configuration that looks like `2 [m] 3` where `m` is a 1448032-bit odd integer, and still has not halted.

In the long-term behavior of this TM, the machine tends to be in one of seven kinds of configurations: ``` [B0] 3s 2 [B1] 3s [B1] 3s B [B] 3s 1 [B0] B 3s B [0] B 3s 2 [B1] B 3s ``` Here, `B` is some big number, `B0` is a big even number, `B1` is a big odd number, and `3s` is a small multiple of 3 and `3s >= 0`.

There are 15 kinds of transitions between these configurations using rules `e, f, h, j, k, l, m, n` as shown in this diagram here.

There are either one or two big numbers in the list. When there are two big numbers, the left big number might get smaller and smaller and if it reaches 3, then the machine halts by rule `c` or `i`. This could happen if the machine keeps going between configurations `B [B] 3s`, `1 [B0] B 3s`, `B [0] B 3s`. The red arrows in the diagram make the left big number significantly smaller and the green arrows make it larger. However, the machine most likely will reset back to a configuration with only one big number. As the machine continues, the numbers grow rapidly, thanks to the `j` rule basically multiplying a number by 3, such that it becomes increasingly unlikely for the machine to halt -- the TM would need to have a long sequence of the correct transitions and avoid resetting.

To get a sense of how likely any tape configuration is to halt, I ran simulations starting from `[m]` for various values of `m`. Either the simulation halts relatively quickly or the numbers get too big and overflow (I'm using 128-bit integers here). The simulation quickly halts for the following values of `m`: ``` 3, 10, 12, 27, 28, 33, 34, 35, 36, 43, 45, 48, 65, 74, 79, 81, 82, 88, 92, 98, 122, 128, 132, 138, 178, 186, 188, 192, 202, 210, 213, 230, 235, 236, 275, 276, 294, 348, 394, 408, 455, 474, 516, 529, 539, 544, 632, 653, 698, 723, 736, 748, 754, 768, 818, 859, 901, 981, 1003, 1116, 1297, 1358, 1372, 1522, 1580, 1610, 1668, 1689, 1822, 1825, 1882, 1933, 1952, 1990, 2038, 2052, 2074, 2162, 2277, 2286, 2364, 2490, 2496, 2507, 2570, 2578, 2696, 2778, 2848, 2914, 2936, 2982, 3002, 3058, 3072, 3196, 3387, 3421, 3517, 3540, ... ```

I made a list of quickly halting values of `m` up to 10^9. It seems like the number of quick halters less than or equal to `x` goes as approximately `6.4 * x^0.350`. See plot.

So maybe the density of quickly halting values is low enough that the TM is nonhalting (though difficult to prove)?

However there is also some structure to the sequence of quickly halting values, so maybe more analysis is needed. Here is a plot of gaps between quickly halting values.