Is halting problem for /// solvable assuming programs that maches the regex "^/[ab]*/[ab]*/[ab]*$"?

/// is an esoteric language, and I thought of posting a code-golf problem related to it.

A /// program of the form /p/q/r where p, q, and r are strings that do not contain / or \ does:

• If the string p is a substring of r, go to step 2; otherwise step 5.

• Replace the leftmost occurrence of p in r with q.

• Let the result of step 2 be the new r.

• Go to step 1.

• Output r and halt.

In step 1, an empty string shall be a substring of any strings.

For simplicity I am thinking each of p, q, r consisting of zero or more a's and b's.

At first I thought the following algorithm would work:

• Returns no if p is both a substring of q and r; otherwise yes.

But that was wrong; /ab/bbaa/abb can be one of the exceptions, as "ab" does not appear in "bbaa" but in "abb".

I am suspecting it's possibly impossible to make an algorithm to solve this problem. Is it solvable?

According to this Math Overflow answer, the answer is not known as of 2014.

It seems your problem can be restated to asking if the termination of one-rule string-rewriting systems is decidable. A rule of a string-rewriting system is a substitution like the one you gave with $ab\to bbaa$.

Even though the Math Overflow answer doesn't distinguish between alphabet size, which in your case is only 2 consisting only of $\{a,b\}$, you can convert a SRS with a larger alphabet into one with only 2 letters, thus making their termination problems equivalent. Basically, give each letter a unique index $n$, then replace it with $ab^na$ in both the input string as well as the rules. So for example $cad→addc$ can be encoded as $abbbaabaabbbba→abaabbbbaabbbbaabbba$.

StackExchange Computer Science Q#141979, answer score: 4