# Question about the XOR function on two binary strings

Nota bene: Just so you're aware, being no avid mathematician, I might start making up terminology in this question to make what I'm asking a little more clear.

Define a set $$C$$ of infinitely long binary strings so that $$C_0=000000000000...$$ $$C_1=111111111111...$$ $$C_2=101010101010...$$ $$C_3=110011001100...$$ $$C_4=111000111000...$$ $$C_5=111100001111...$$ and so every $$C_n$$ for $$n\ge2$$ is equivalent to $$n-1$$ ones followed by $$n-1$$ zeroes followed by $$n-1$$ ones, and so on.

Now define a function $$\Psi(C_n,q)$$ taking one member of $$C$$ and a non-negative integer $$q$$ as an argument. The function $$\Psi$$ will operate on the binary string $$C_n$$, returning another binary string which consists of $$C_n$$ shifted to the left by $$q$$ elements. For example: $$\Psi(C_4,2)=100011100011...$$

Finally, define the XOR operation $$A\oplus B$$ as operating on any two binary strings $$A$$ and $$B$$ with infinite length. This operation will perform the XOR function on each pair of corresponding members of $$A$$ and $$B$$, and return the result. This is hard to put into words, so here is an example:

$$1010101...\oplus 1101101...=0111000...$$

An infinitely long binary string $$U$$ is said to be comprehensible if it can be expressed as $$\Psi(C_m,p)\oplus\Psi(C_n,q)$$ for any two elements of $$C$$, $$C_m$$ and $$C_n$$, and any two non-negative integers, $$p$$ and $$q$$. What is the shortest finite binary string that cannot begin a comprehensible infinitely long binary string, if any exist?

• Hi. Can someone explain why this was downvoted? Commented Nov 28, 2019 at 1:07
• An example is insufficient. Do you mean bitwise XOR, 0 + 0 = 0, 0 + 1 = , 1 + 0 = 1, 1 + 1 = 0 (addition modulus 2)? Commented Nov 28, 2019 at 2:54
• @William Elliot Precisely. Commented Nov 29, 2019 at 3:03
• What is the origin of this question? Commented Nov 29, 2019 at 8:51
• @J.-E.Pin There's a chance this question could be in some mathematical text somewhere, but I initially made this question up in my head. Putting it in a mathematical format was slightly difficult for me, but I think I managed to do it. Commented Nov 29, 2019 at 21:02

For words of length $$k$$ we only need to consider $$q\le 2n$$ and $$n\le k$$. So at most $$(2k^2)^2$$ possible XORs of such words. So when $$(2k^2)^2<2^k$$ then an example exists of length $$k$$. In particular $$k=19$$ is short enough to find an example.