How can I catalog these generalized Collatz problems?

Question

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

$4 \times x \times y + 6 \times x + 6 \times y + 9 \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 \times p$

$p \times p + 2 \times p \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 some fixed $\ell$ is in $\text{NP}$ (because factoring is also in $\text{NP}$ and we can produce a $(\log(x) + \log(y))^{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 an $\text{NP}$-hard problem on rulesets. The former property of constant paths being in $\text{NP}$, however useful it may or may not be in explaining the overall situation, is preserved by certain extensions (for example if we introduce variables taking square-free values, or variables with implicit order constraints) but is not preserved by others (such as a $2^x$ operator which would permit short paths with small endpoints and large intermediate values).

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?

Answer 1

This is a ruleset whose termination is independent from $\mathrm{PRA}$, primitive recursive arithmetic, letting $\langle x,y\rangle$ be short for $(x+y)(x+y+1)+2y$:

$\langle y,\langle 0,z+1\rangle\rangle \rightarrow \langle y+1,z+1\rangle;$

$\langle 0,\langle x+1,z\rangle\rangle \rightarrow \langle 1,\langle x,z\rangle\rangle;$

$\langle y+1,\langle x+1,z\rangle\rangle \rightarrow \langle y,\langle x+1,\langle x,z\rangle\rangle\rangle;$

$\langle y,0\rangle \rightarrow 1;$

$\langle y,2\times x+1\rangle \rightarrow 1;$

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

When expanded out, this gives a ruleset with at most $988$ characters.

The Ackermann function is a function whose totality is independent from $\mathrm{PRA}$. This section of its Wikipedia article describes a stack-based method of computing it. This implementation is based on this method, except with a few differences:

• Nested pairs are used instead of a stack, using the function $(x+y)(x+y+1)+2y$. This is the doubling of Cantor's pairing function and is a bijection from $\mathbb N^2$ to the set of nonnegative even integers. Only nonnegative even integers can be unpaired, so the only numbers used by this system are nonnegative even integers, and $1$ to signal termination.
• The order in which the stack is written is reversed (to lower symbol count), and there is a permanent extra entry (e.g. $1$) at the end. For example the article lists the stack $4,5,3$ as corresponding to $A(4,A(5,3))$, here $\langle 3,\langle 5,\langle 4,1\rangle\rangle\rangle$ is used, where the rightmost $1$ is the permanent entry. (The permanent entry is included to pad out stack length, so that the stack's length doesn't drop below $3$ until termination is intended.)
• The first rule uses $\langle y,\langle 0,z+1\rangle\rangle$ instead of $\langle y,\langle 0,z\rangle\rangle$, to enforce that $z$ is not zero, to prevent overlap with the $\langle y,0\rangle$ rule (about overlap, see lemma 1 below).
• Termination is not when the stack reaches length $1$, but when it reaches length $2$, determined by when the second entry in the stack is $0$ or an odd number. (Technically, if the stack is $\langle y,0\rangle$, this could be read as $\langle y,\langle 0,0\rangle\rangle$, $\langle y,\langle 0,\langle 0,0\rangle\rangle\rangle$, etc., but this is disallowed.)
• After computation is finished, instead of returning the final value, the rewrite system goes to $1$ to indicate termination.

All odd natural numbers get sent directly to $1$, as they are not unpairable. $\langle 0,0\rangle$ is also sent to $1$, as otherwise we would have the nonterminating sequence $\langle 0,0\rangle = \langle 0,\langle 0,0\rangle\rangle \rightarrow \langle 1,0\rangle = \langle 1,\langle 0,0\rangle\rangle \rightarrow \langle 2,0\rangle = \ldots$.

---

In order to show its termination is equivalent to the Ackermann function, we introduce some terminology for use in eliminating cases. I have attempted to make this section formalizable in $\mathsf{PRA}$, although I have not checked all details.

Lemma 1: For each natural number $z$, there is exactly one rewrite rule which applies to $z$.

Proof: By cases on $z$. If $z$ is odd, the only rule applying is the last rule, as all outputs of $\langle\bullet,\bullet\rangle$ are even. From here assume $z$ is even. As $\langle x,y\rangle$ is a bijection from $\mathbb N^2$ to the set of even natural numbers, there are unique $x,y\in\mathbb N$ such that $z=\langle x,y\rangle$. If $y$ is odd, then the only rule that applies is the fifth, as rules #1 through #4 all assume $y$ is of the form $\langle y_1,y_2\rangle$ and therefore even. From here assume $y$ is even, and decompose $y$ into $\langle y_1,y_2\rangle$. If $y=0$, then the fourth rule applies, as rules #1 through #3 require nonzero $y$. From here assume $y$ is nonzero. If $y_1=0$, then the first rule applies, and if $y_1>0$, then either the second or third rule applies. The choice between second and third rule is determined by whether $x$ is zero or not. $\square$

Corollary: For each $n\in\mathbb N$ there is a unique natural number which the ruleset maps $n$ to. Call this number $\pi(n)$, and for natural number $k$ define $\pi^k(n)$ by $\pi^0(n)=n$, $\pi^{k+1}(n)=\pi(\pi^k(n))$.

For an even positive integer $x$, define $\mathrm{rightmost}(x)$ to be $y$ such that $x=\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle$, where natural numbers $n$, $x_0,\ldots,x_n,y$ are chosen such that $n$ is minimal where $x=\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle$ and $y$ is $0$ or an odd integer. This decomposes the right component of $x$ until either no longer possible or stopping short of the infinite loop $0=\langle 0,0\rangle=\langle 0,\langle 0,0\rangle\rangle=\ldots$, and returns the very rightmost component. Define $\mathrm{length}(x)$ to be the natural number $n$. (E.g. $\mathrm{rightmost}(\langle 3,\langle 4,5\rangle\rangle)=5$, and $\mathrm{length}(\langle 3,\langle 4,5\rangle\rangle)=2$.)

Lemma 2: Let $n$, $x_0,\ldots,x_n$ be natural numbers, and $y$ be an odd natural number. The ruleset terminates on $\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle$ iff it terminates on $\langle x_0,\langle x_1,\ldots\langle x_n,0\rangle\ldots\rangle\rangle$.

Proof: Let $x$ denote $\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle$. We have $\mathrm{length}(x)=n$. If $n=0$, then the fourth and fifth cases apply, and both $\langle x_0,y\rangle$ and $\langle x_0,0\rangle$ map to $1$. If $n>0$, there is no rule sending $\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle$ directly to $1$. It may be proven by induction on $k$ that if $\mathrm{length}(\pi^k(x))>0$, then $\pi^k(\langle x_0,\langle x_1,\ldots\langle x_n,y\rangle\ldots\rangle\rangle)$ is equal to $\pi^k(\langle x_0,\langle x_1,\ldots\langle x_n,0\rangle\ldots\rangle\rangle)$, using the fact that while $\mathrm{length}(x)>0$ the only applicable rules are the first three, which preserve $\mathrm{rightmost}(x)$. $\square$

If I have implemented it correctly, for $x,y\geq 0$, $A(x_0,A(x_1,\ldots A(x_{n-1},x_n)\ldots))$ is defined iff the ruleset terminates with starting value $\langle x_n,\langle x_{n-1},\ldots\langle x_1,\langle x_0,1\rangle\rangle\ldots\rangle\rangle$. This leads to the following:

Claim: This ruleset terminates on all $x\in\mathbb N$ iff the Ackermann function is total on all inputs.

Proof sketch: ($\rightarrow$) Termination of the stack implmentation of the value $A(x_1,x_0)$ of the Ackermann function is equivalent to termination of the ruleset on $x=\langle x_0,\langle x_1,1\rangle\rangle$. ($\leftarrow$) Assume that the Ackermann function is total. Let $x\in\mathbb N$ be arbitrary. If $x=0$, $x$ is an odd number, or $x$ is of the form $\langle x_0,y\rangle$ where $y$ is odd, then the ruleset terminates on $x$ by one of the last three rules in the ruleset. From here assume that $x$ is of the form $\langle x_0,y_0\rangle$ where $y_0>0$ is even. Repeatedly unpair $x$ to obtain $x=\langle x_0,\langle x_1,\ldots\langle x_k,y\rangle\ldots\rangle\rangle$, where $k$ is minimum possible such that $y$ is $0$ or odd. By lemma 2 the ruleset terminates on $\langle x_0,\langle x_1,\ldots\langle x_k,y\rangle\ldots\rangle\rangle$ iff it terminates on $\langle x_0,\langle x_1,\ldots\langle x_k,1\rangle\ldots\rangle\rangle$, so termination on $x$ is equivalent to the definedness of $A(x_k,A(x_{k-1},\ldots A(x_1,x_0)\ldots))$.

---

Writing a similar system for $\mathrm{PA}$ using this method would be difficult. The best approach may be Beklemishev's worm game, which is related to Goodstein's theorem. (L. D. Beklemishev, "The Worm Principle", 2003)