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 we can construct some very short rulesets describing various number theory problems. For example, here is the Goldbach conjecture:

$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;$

That there are such expressions is not surprising to me, but I am intrigued by the fact that they are so short, and particularly that the last two (the shortest) have very large first counterexamples. So I was thinking why not 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.

Can we build a small ruleset whose convergence is equivalent to some complexity class separation or equivalence like $\text{P} = \text{NP}$? Otherwise is there any simple extension of the language that can express this? I don't see any obstruction since these are usually $\Pi_2$ sentences like twin primes.

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? In this context "trivial" means something like "is an odd composite" as in the third example. One general fact I deduced is this: the question of whether there exists a path from $x$ to $y$ with length less than $\ell = (\log(x) + \log(y))^k$ for fixed $k$ is in $\text{NP}$ (because factoring is also in $\text{NP}$ and we can produce an $\ell^{O(1)}$-bit certificate showing how the numbers in the path match the rules). 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}$-complete (independently of whether or not we allow prime variables in the ruleset).

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 small, although I don't think I'll have enough computer power to consider every well-formed string up to this length. But there are lots of symmetries, redundancies, and easy proofs, so it is possible to reduce the space significantly.

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?