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?

  • $\begingroup$ Hi. Can someone explain why this was downvoted? $\endgroup$
    – Cloudy7
    Commented Nov 28, 2019 at 1:07
  • 1
    $\begingroup$ An example is insufficient. Do you mean bitwise XOR, 0 + 0 = 0, 0 + 1 = , 1 + 0 = 1, 1 + 1 = 0 (addition modulus 2)? $\endgroup$ Commented Nov 28, 2019 at 2:54
  • $\begingroup$ @William Elliot Precisely. $\endgroup$
    – Cloudy7
    Commented Nov 29, 2019 at 3:03
  • $\begingroup$ What is the origin of this question? $\endgroup$
    – J.-E. Pin
    Commented Nov 29, 2019 at 8:51
  • $\begingroup$ @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. $\endgroup$
    – Cloudy7
    Commented Nov 29, 2019 at 21:02

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .