Return to Question

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

 

$x + x \rightarrow x;$

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

 

$x + x \rightarrow x;$

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

$p + q \rightarrow 1;$

 

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

 

$2 \rightarrow 1;$

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

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

 

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

 

$ p \rightarrow 1;$

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

 

$p \rightarrow 1;$

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

 

$p \rightarrow 1;$

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

$x + x \rightarrow x;$

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

$x + x \rightarrow x;$

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

$p + q \rightarrow 1;$

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

$2 \rightarrow 1;$

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

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

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

$ p \rightarrow 1;$

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

$p \rightarrow 1;$

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

$p \rightarrow 1;$

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, however useful it may be in explaining this 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).

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

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 $\text{NP}$-complete (independently of whether or not we allow prime variables in the ruleset). This property, however useful it may be in explaining this 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).

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, however useful it may be in explaining this 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).