2
$\begingroup$

Suppose that I have a bit string of finite length. Is there any bit rewriting rule rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit), that doesn't change the total count of 1s on the bit string, and that when applied to arbitrary triplets in any order will converge to a bit string that will begin with an arbitrarily long sequence of 10, followed by either all 0s or all 1s.

$\endgroup$
  • $\begingroup$ Don't you need to assume that the input has the same number of 0s and 1s? $\endgroup$ – Yuval Filmus May 4 '16 at 16:27
  • $\begingroup$ @YuvalFilmus I understand what you mean and edited the question with a more precise spec. $\endgroup$ – MaiaVictor May 4 '16 at 16:31
  • $\begingroup$ Your fix doesn't work. In your example below you do have consecutive zeroes. $\endgroup$ – Yuval Filmus May 4 '16 at 16:38
  • $\begingroup$ @YuvalFilmus woops. You are correct. I think it is fixed now, but I think it is more verbose than it shcoulduld be. Any idea? $\endgroup$ – MaiaVictor May 4 '16 at 16:51
  • $\begingroup$ No, it still doesn't work. This would allow 10010000000 instead of 1010000000000. In fact, your rules converge to a string of the form $0^*+1(01)^*0^*$. $\endgroup$ – Yuval Filmus May 4 '16 at 16:58
3
$\begingroup$

Seems like the rule:

000 => 000
001 => 100
010 => 010
100 => 100
011 => 011
101 => 101
110 => 101
111 => 111

Does what I want. Testing this rule by applying it to an arbitrary bit string, this is how it evolves:

0   11110110010010000010100000000001000
1   11110111001000001000100000000001000
2   11101111100000100000100000000100000
3   11101111100010000010000000010000000
4   11011111011000001000000001000000000
5   11011111011000100000000100000000000
6   10111110110110000000010000000000000
7   10111110110110000001000000000000000
8   10111101101101000100000000000000000
9   10111101101101010000000000000000000
10  10111011011011010000000000000000000
11  10111011011011010000000000000000000
12  10110110110110110000000000000000000
13  10110110110110110000000000000000000
14  10101101101101101000000000000000000
15  10101101101101101000000000000000000
16  10101011011011011000000000000000000
17  10101011011011011000000000000000000
18  10101010110110110100000000000000000
19  10101010110110110100000000000000000
20  10101010101101101100000000000000000
21  10101010101101101100000000000000000
22  10101010101011011010000000000000000
23  10101010101011011010000000000000000
24  10101010101010110110000000000000000
25  10101010101010110110000000000000000
26  10101010101010101101000000000000000
27  10101010101010101101000000000000000
28  10101010101010101011000000000000000
29  10101010101010101011000000000000000
30  10101010101010101010100000000000000
31  10101010101010101010100000000000000
32  10101010101010101010100000000000000
33  10101010101010101010100000000000000
34  10101010101010101010100000000000000
35  10101010101010101010100000000000000
36  10101010101010101010100000000000000
37  10101010101010101010100000000000000
38  10101010101010101010100000000000000
39  10101010101010101010100000000000000
40  10101010101010101010100000000000000
41  10101010101010101010100000000000000
42  10101010101010101010100000000000000
43  10101010101010101010100000000000000
44  10101010101010101010100000000000000
45  10101010101010101010100000000000000
46  10101010101010101010100000000000000
47  10101010101010101010100000000000000
48  10101010101010101010100000000000000
49  10101010101010101010100000000000000
50  10101010101010101010100000000000000
51  10101010101010101010100000000000000
52  10101010101010101010100000000000000
53  10101010101010101010100000000000000
54  10101010101010101010100000000000000
55  10101010101010101010100000000000000
56  10101010101010101010100000000000000
57  10101010101010101010100000000000000
58  10101010101010101010100000000000000
59  10101010101010101010100000000000000
60  10101010101010101010100000000000000
61  10101010101010101010100000000000000
62  10101010101010101010100000000000000
63  10101010101010101010100000000000000
64  10101010101010101010100000000000000
65  10101010101010101010100000000000000
66  10101010101010101010100000000000000
67  10101010101010101010100000000000000
68  10101010101010101010100000000000000
69  10101010101010101010100000000000000
70  10101010101010101010100000000000000
71  10101010101010101010100000000000000
72  10101010101010101010100000000000000
73  10101010101010101010100000000000000
74  10101010101010101010100000000000000
75  10101010101010101010100000000000000
76  10101010101010101010100000000000000
77  10101010101010101010100000000000000
78  10101010101010101010100000000000000
79  10101010101010101010100000000000000
80  10101010101010101010100000000000000
81  10101010101010101010100000000000000
82  10101010101010101010100000000000000
83  10101010101010101010100000000000000
84  10101010101010101010100000000000000
85  10101010101010101010100000000000000
86  10101010101010101010100000000000000
87  10101010101010101010100000000000000
88  10101010101010101010100000000000000
89  10101010101010101010100000000000000
90  10101010101010101010100000000000000
91  10101010101010101010100000000000000
92  10101010101010101010100000000000000
93  10101010101010101010100000000000000
94  10101010101010101010100000000000000
95  10101010101010101010100000000000000
96  10101010101010101010100000000000000
97  10101010101010101010100000000000000
98  10101010101010101010100000000000000
99  10101010101010101010100000000000000
100 10101010101010101010100000000000000
101 10101010101010101010100000000000000
102 10101010101010101010100000000000000
103 10101010101010101010100000000000000
104 10101010101010101010100000000000000
105 10101010101010101010100000000000000
106 10101010101010101010100000000000000
107 10101010101010101010100000000000000
108 10101010101010101010100000000000000
109 10101010101010101010100000000000000
110 10101010101010101010100000000000000
111 10101010101010101010100000000000000
112 10101010101010101010100000000000000
113 10101010101010101010100000000000000
114 10101010101010101010100000000000000
115 10101010101010101010100000000000000
116 10101010101010101010100000000000000
117 10101010101010101010100000000000000
118 10101010101010101010100000000000000
119 10101010101010101010100000000000000
120 10101010101010101010100000000000000
121 10101010101010101010100000000000000
122 10101010101010101010100000000000000
123 10101010101010101010100000000000000
124 10101010101010101010100000000000000
125 10101010101010101010100000000000000
126 10101010101010101010100000000000000
127 10101010101010101010100000000000000

This was found by testing every possible automata, writing the results to a file and then manually inspecting to look for the desired outcome. This is the resulting file and this is the script I used to generate it:

// count-preserving rules
var C0 = [[0,0,0]];
var C1 = [[0,0,1], [0,1,0], [1,0,0]];
var C2 = [[0,1,1], [1,0,1], [1,1,0]];
var C3 = [[1,1,1]];

function rewrite(bits, i, rules){
    var A = rules[0], B = rules[1], C = rules[2], D = rules[3], E = rules[4], F = rules[5];
    switch ((bits[i]<<2) + (bits[i+1]<<1) + bits[i+2]) {
        case 0b000: bits[i] = 0; bits[i+1] = 0; bits[i+2] = 0; break; // 000
        case 0b001: bits[i] = C1[A][0]; bits[i+1] = C1[A][1]; bits[i+2] = C1[A][2]; break;
        case 0b010: bits[i] = C1[B][0]; bits[i+1] = C1[B][1]; bits[i+2] = C1[B][2]; break;
        case 0b100: bits[i] = C1[C][0]; bits[i+1] = C1[C][1]; bits[i+2] = C1[C][2]; break;
        case 0b011: bits[i] = C2[D][0]; bits[i+1] = C2[D][1]; bits[i+2] = C2[D][2]; break;
        case 0b101: bits[i] = C2[E][0]; bits[i+1] = C2[E][1]; bits[i+2] = C2[E][2]; break;
        case 0b110: bits[i] = C2[F][0]; bits[i+1] = C2[F][1]; bits[i+2] = C2[F][2]; break;
        case 0b111: bits[i] = 1; bits[i+1] = 1; bits[i+2] = 1; break; // 111
    };
};

function show(bits){
    return bits.map((n)=>n?"1":"0").join("");
};

function test(times, rules, bits){
    show_rule = (r) => ""+r[0]+""+r[1]+""+r[2];
    var str 
        = JSON.stringify(rules)+"!\n"
        + "001=>"+show_rule(C1[rules[0]])+", "
        + "010=>"+show_rule(C1[rules[1]])+", "
        + "100=>"+show_rule(C1[rules[2]])+", "
        + "011=>"+show_rule(C2[rules[3]])+", "
        + "101=>"+show_rule(C2[rules[4]])+", "
        + "110=>"+show_rule(C2[rules[5]])+"\n";
    for (var t=0; t<times; ++t){
        for (var i=0; i<bits.length-(t%3); i+=3)
            rewrite(bits, i+(t%3), rules);
            //rewrite(bits, ~~(Math.random()*(bits.length-2)), rules);
        str += t + "\t" + show(bits) + "\n";
    };
    return str;
};

var str = "";
for(var A=0;A<3;++A)for(var B=0;B<3;++B)for(var C=0;C<3;++C)for(var D=0;D<3;++D)for(var E=0;E<3;++E)for(var F=0;F<3;++F){
    var block = test(128, [A,B,C,D,E,F], [1,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]);
    str += block + "\n";
};
require("fs").writeFileSync("count_preserving_binary_cellular_automatas.txt", str);
//document.getElementById("automata_result").value = str;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.