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](https://mathoverflow.net/questions/216358/relaxed-collatz-3x1-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](https://mathoverflow.net/questions/205911/a-collatz-like-function-that-bifurcates-on-primes):

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

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 $(\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}$-complete (whether or not we allow prime variables). 

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?