The Collatz conjecture can be expressed in terms of a ruleset in the language $\{x,+,1,\rightarrow,;\}$:

$x + x + 1 \rightarrow x+x+x+1+1;$

$x + x \rightarrow x;$

Whenever a number matches the LHS of a rule, it can be replaced with the RHS. The Collatz conjecture is that we can always get to $1$ with the above ruleset. Conway proved that a similar generalization is universal. But the ruleset here doesn't have to be a single function — the "relaxed" Collatz conjecture can be expressed this way too:

$x \rightarrow x + x + x + 1;$

$x + x \rightarrow x;$

My question is about when we extend this language with a multiplication symbol $\times$, subtraction symbol $-$, additional natural number variables $y, z, \dots$ and variables $p, q, r \dots$ restricted to taking prime values. Now we can also represent this prime-bifurcating Collatz-like function:

$p \rightarrow p \times p;$

$2 \times x \rightarrow x;$

$(2 \times x + 3) \times (2 \times y + 3) \rightarrow 2 \times x \times y + 3 \times x + 3 \times y + 4;$

And even better, we can now make some very short rulesets describing various number theory problems. For example, here is Goldbach:

$p + q \rightarrow 1;$

$2 \times x + 1 \rightarrow 1;$

$2 \rightarrow 1;$

Infinitely many twin primes:

$p \rightarrow p \times (p-2);$

$p \times (p+2) \rightarrow 1;$

$3 \times x \rightarrow 3 \times x + 1;$

$3 \times x + 1 \rightarrow 3 \times x + 4;$

$3 \times x +2 \rightarrow 3 \times x + 4;$

Infinitely many primes of the form $n^2+1$:

$x \rightarrow x \times x + 1;$

$ x \times x + 1 \rightarrow x \times x + 2 \times x + 2;$

$ p \rightarrow 1;$

Existence of Sierpinski numbers:

$x \rightarrow 2 \times x - 1;$

$p \rightarrow 1;$

Existence of Riesel numbers:

$x \rightarrow 2 \times x + 1;$

$p \rightarrow 1;$

The existence of these expressions is not very surprising to me, but I am intrigued by the fact that they are so short, and also that the last two (the shortest) have very large first counterexamples. So I'd like to look at all short rulesets and see how they can be categorized. For example, I'd like to know the shortest ruleset with possibly undecidable convergence. I'd also like to be able to characterize some of the decidable ones.

Is there a short ruleset whose convergence is undecidable in PA? I know we can state Goodstein's theorem with a new base-bumping symbol but I wonder if that's necessary. Similarly, is there a short ruleset whose convergence is equivalent to the existence of infinitely many Mersenne primes? I found the Riesel number example while trying to construct one — it seems like a new symbol for exponentiation is needed for this. In both cases I understand Conway's construction gives a ruleset whose convergence is equivalent, but it won't be a very short one.

And aside from whether all numbers converge, is there a short ruleset whose convergence from any starting point corresponds to some non-trivial property of that starting point? One general fact I deduced is this: the question of whether there exists a chain from $x$ to $y$ with length less than $(\log{(x)} + \log{(y))^k}$ is in $\text{NP}$ (because factoring is also in $\text{NP}$). And in the other direction we can arithmetize a $\text{SAT}$ instance into a single rule, so deciding if $2 \rightarrow 1$ is $\text{NP}$-hard.

A compact way of representing a ruleset that I'm considering is this, using the twin primes example: p>*pp*-p*-p,*pppp>1,nnn>nnn1,nnn1>nnn1111,nnn11>nnn1111. Here I'm making addition implicit in concatenation and using - as a symbol for $-1$. This keeps the alphabet limited, although I still don't think I have enough computer to consider everything this long.

If I write a program to analyze all short rulesets, what should I make it look for to help me get some insight into these issues?