18
$\begingroup$

Consider the following $2$-tag system:

$$\begin{cases}a\rightarrow abc\\b\rightarrow ab\\c\rightarrow c\end{cases}$$

In brief, a $2$-tag system is a Turing-complete string substitution system wherein you check the current first letter against the rules given, append the corresponding letters (e.g. $a$ maps to $abc$) to the end of the string, and then remove the first two letters from the string. Repeat until string disappears or cycle is detected.

I assert that for any starting string $(abc)^{k}$, this system will always cycle back to $(abc)^k$.

e.g. for $k=1$:

abc
  cabc
    bcc
      cab
        bc
          ab
            abc

I am fairly certain this is true but can't prove it.

If anyone can provide a proof, counterexample, or persuasive argument for or against its validity, I'll consider this answered.

I also suspect there's no easy way to calculate the period of the cycle and would welcome input on that too. For reference, the first 25 periods (courtesy of r.e.s.) are:

$\{6, 24, 78, 96, 63, 1030, 6558, 3936, 5922, 75756, 40474, 1594320, 79630, 7166907, 837353,\\1311364, 9620370, 6835198, 577674197, 2092070640, 784506057, 1116341675, 282429536478, 11933733565, 169161110854\}$

My gut sense is that this is not really a Collatz-level problem; the fact that it's in a fairly well-behaved bounded cycle suggests to me that by gluing a few of these rules together properly, it should be provable that $(abc)^k$ necessarily repeats. That said, my gut is often bad at number theory.


Some observations

The number of $b$'s is fixed at $k$, and they're always preceded by $a$, unless it's a $b$ at the start of the string. At each end of the string, and between every $b$ and $a$, there may be between $0$ and $2$ $c$'s, and the way they float around and interact with parity seems like what drives the cycles. Those constraints can be confirmed by establishing that, bottom line, the only unique substrings you can generate within this system are $\{ab,abc,abcc\}$. All possible strings reachable from $(abc)^k$ will be some combination of those pasted together, possibly with a wraparound truncation to start. You can confirm this via inspection or with the "table method" described in De Mol (2010).

This provides a strict lower bound of $2k/3$ for the length of the shortest word in the cycle (note that $(ab)^k$ always appears), with $4k/3$ as the upper bound on word length. We can take a stab at an upper bound on period by treating $b$ as dividing the string into $k+1$ partitions, each of which contains $0$ to $2$ $c$'s, yielding at most $3^{k+1}$ unique configurations. Since the combination of leading and trailing $c$'s can't exceed two, we eliminate the possibilities $\{ccScc,cScc,ccSc\}$. This leaves us with an upper bound of $$f(k) := 3^{k+1}-3.$$

This seems to work well for small $k$ and provides the exact period for $k \in \{1,2,3,7,12,23\}$, which is as high as I can confirm.

$\endgroup$
9
  • $\begingroup$ What is the meaning of these arrows? $\endgroup$
    – Michael
    Mar 9, 2021 at 4:33
  • 4
    $\begingroup$ @Michael You delete the first two elements in the string, then append to the end of the string whatever the first element of the string mapped to by the arrow $\endgroup$
    – Jbag1212
    Mar 9, 2021 at 4:59
  • 1
    $\begingroup$ FWIW, here's a directly computed list of the first 25 periods: [6, 24, 78, 96, 63, 1030, 6558, 3936, 5922, 75756, 40474, 1594320, 79630, 7166907, 837353, 1311364, 9620370, 6835198, 577674197, 2092070640, 784506057, 1116341675, 282429536478, 11933733565, 169161110854]. $\endgroup$
    – r.e.s.
    Mar 10, 2021 at 13:28
  • 2
    $\begingroup$ If Collatz conjecture can be proven elementarily, I believe that it will be proven using a form of induction we haven't constructed yet (constructed in a sense like the Fundamental Thm of Arithmetic allows for a 'multiplicative' form of induction). The question here is similar, and I'm attempting it. Failure is most likely for me, but I hope this direction is helpful. $\endgroup$
    – Poypoyan
    Mar 11, 2021 at 23:02
  • 1
    $\begingroup$ @Trevor I used PyPy to run a simple Python program that performed the tag operations until the initial word was repeated. (The longer periods took quite a while; e.g. about $5$ hrs for $k=23$). $\endgroup$
    – r.e.s.
    Mar 12, 2021 at 15:37

1 Answer 1

11
+50
$\begingroup$

We write $U = ab, V = abc, W = abcc$.


Definition:

  • A nonempty string will be called "regular" if it is the concatenation of finitely many copies of $U, V, W$.

  • If $X$ is any regular string, then we write $X'$ for the string obtained from $X$ by removing the leading $a$. Such a string will be called "quasi-regular".

  • A "normal" string is a string that is regular or quasi-regular.


The system can then be translated to a system on normal strings.

More precisely, we have the following rules (*): \begin{eqnarray} UX &\rightarrow& XV\\ VX &\rightarrow& X'W\\ WX &\rightarrow& XW\\ U'X &\rightarrow& X'U\\ V'X & \rightarrow& XU\\ W'X & \rightarrow& X'V \end{eqnarray} where $X$ denotes any regular string.

Note that this rule is injective: from the resulting string, we can deduce what the original string is.


Definition:

  • The "weight" of a regular string is the total number of $U, V, W$ in the string.
  • The weight of a quasi-regular string is the weight of the regular string it comes from.

(Equivalently, the weight of any normal string is just the number of $b$'s appearing in it.)


It is obvious from the above rules that the weight of a normal string does not change after applying the rules.

Therefore, starting from any normal string, the generated system can have only finitely many possible strings.

Since the procedure continues forever, the system is eventually periodic.

However, the rule being injective, the system must be purely periodic, hence will eventually return to the initial status.

This works for any normal string. In particular, it works for the string $V^k$.


(*)There is an exception when $X$ is the empty string, which we exclude here.

$\endgroup$
5
  • 1
    $\begingroup$ It looks like you wrote up the thoughts I was trying and failing to formalize just now... that if you can run the system effectively unambiguously in reverse, that necessarily implies a cycle that returns to the original value. $\endgroup$
    – Trevor
    Mar 12, 2021 at 18:42
  • $\begingroup$ Confirmed this seems to work perfectly using only the given rules and symbols. Nicely done. $\endgroup$
    – Trevor
    Mar 12, 2021 at 19:20
  • $\begingroup$ Hah beautiful. I had a feeling abstracting away a bit would make it clearer. Great work! $\endgroup$ Mar 12, 2021 at 22:07
  • $\begingroup$ What happens if $X$ contains a $U,V$ or $W$? $\endgroup$
    – JMP
    Mar 13, 2021 at 5:23
  • 1
    $\begingroup$ @JMP It always will; $X$ is a stand-in variable for any number of $U,V$ and/or $W$s concatenated together. $\endgroup$
    – Trevor
    Mar 13, 2021 at 6:06

You must log in to answer this question.

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