Piecewise Affine Function

A Piecewise Affine Function (PAF) is a piecewise-defined function where each case is affine (and the case constraints are polyhedra). Many Cryptids are modeled by iterated PAFs, for example, BMO1. Like Generalized Collatz Problems, iterated PAFs are also proven to be Turing complete. On the bbchallenge Discord, these were originally called "Linear-Inequality Affine Transformation Automata (LIATA)" before we knew about the existing name in published literature.

Formal Definition

A n-dimension, p-region PAF is a piecewise defined partial function $f:{\mathbb{\mathbb{Z}}}^n\to {\mathbb{\mathbb{Z}}}^n$:$$f(\overrightarrow{x})=\{\begin{array}{ll}{f}_0(\overrightarrow{x})& \text{for }\overrightarrow{x}\in H_0\\ f_1(\overrightarrow{x})& \text{for }\overrightarrow{x}\in H_1\\ & ⋮\\ f_{p-1}(\overrightarrow{x})& \text{for }\overrightarrow{x}\in H_{p-1}\\ \end{array}$$Where each $f_i(\overrightarrow{x})=A_i\overrightarrow{x}+\overrightarrow{b_i}$ is an affine function and the $H_i\subset {\mathbb{\mathbb{Z}}}^n$ are non-overlapping "polyhedral regions" (defined below). If $\overrightarrow{x}$ is not in any region $H_i$, we say that it halts on that configuration.

We define a closed, rational half-space to be a region $\{\overrightarrow{x}\in {\mathbb{ℝ}}^n:\overrightarrow{c}\cdot \overrightarrow{x}+d\ge 0\}$ for some $\overrightarrow{c}\in {\mathbb{\mathbb{Q}}}^n$ and $d\in \mathbb{\mathbb{Q}}$. In other words, it is the half of n-dimensional Euclidean space on one side of a hyperplane (a subspace defined by an affine function). And let an open, rational half-space be the same thing but using strict inequality ($\{\overrightarrow{x}\in {\mathbb{ℝ}}^n:\overrightarrow{c}\cdot \overrightarrow{x}+d>0\}$).

Finally, define a polyhedral regions (or simply polyhedron) as the intersection of a finite number of rational half-spaces (any combination of closed and open ones). So, for example, the following are all polyhedral regions:

• $a<b$ represented formally as $b-a>0$
• $3a\le b<4a$ represented formally as $(b-3a\ge 0)\wedge (4a-b>0)$
• $a=2$ represented formally as $(a-2\ge 0)\wedge (-a+2\ge 0)$

Given a PAF f, we say that it halts in k steps starting from configuration $\overrightarrow{x}$ iff $f^k(\overrightarrow{x})$ is undefined.

Example

An example of a PAF are the rules for BMO1:$$f(a,b)=\{\begin{array}{ll}(a-b,4b+2)& \text{if }a>b\\ (2a+1,b-a)& \text{if }a<b\end{array}$$where $f(n,n)$ is undefined. BMO1 halts iff there exists k such that $f^k(1,2)$ is undefined (in other words $f^{k-1}(1,2)=(n,n)$ for some n).

This is a 2-dimension, 2-region PAF. The 2 dimensions are the parameters a,b and the two regions are the half-spaces $a<b$ and $a>b$. For each case the parameters are transformed via an affine transformation.

Turing Complete

PAF are Turing complete. This has been proven by implementing Generalized Collatz Problems and Minsky machines as iterated PAF problems: Amir M. Ben-Amram proved in 2015 that 2-dimensional PAF are Turing complete by implementing arbitrary GCP and also that 2-region PAF are Turing complete by implementing arbitrary Minsky machines.

Independently, similar results were proven on the bbchallenge Discord in 2025 (all by reduction to Minsky machines): @Bard proved that 3-dim PAF are Turing complete: Discord link, @star proved that 2-dim PAF are Turing complete: Discord link and Shawn Ligocki wrote up a proof sketch that 2-region PAF are Turing complete: Discord link.

In other words, we know that there exists a Universal PAF (which can simulate all TMs ... and thus all other PAFs) with 2-dimensions and some unspecified number of regions and another with 2-regions and an unspecified number of dimensions. Similar to Universal Turing Machines, we could explore the "pareto frontier" of minimal Universal PAFs by calculating exact values for the number of regions/dimensions in those specific constructions and searching for minimal values here and for more minimal sizes with 3+ dimensions and 3+ regions.

Note: the fact that PAF in general are Turing complete does not prove anything about specific PAF problems. For example, although 2-dim PAF (and 2-region PAF) are known to be Turing complete it is not known if 2-dim, 2-region PAF are. And even if it were known that 2-dim, 2-region PAF are Turing complete, it does not mean that the BMO1 PAF specifically is. And even if the BMO1 PAF specifically was known to be Turing complete, it does not mean that the specific trajectory followed by BMO1 is undecidable. In other words, there is really no hope of using the fact that PAF are Turing complete to prove anything rigorously about a specific example (like BMO1). Instead, the proofs that PAF in general are Turing complete simply provides some intuition for why PAFs in general are probably challenging problems to solve. This is similar to how the proof that Generalized Collatz Problems are Turing complete provides some intuition for why Generalized Collatz Problems in general are probably challenging problems to solve.

References

• Amir M. Ben-Amram. 2015. Mortality of iterated piecewise affine functions over the integers: Decidability and complexity. Computability. 2015;4(1):19-56. doi:10.3233/COM-150032
• Amir M. Ben-Amram, Samir Genaim, and Abu Naser Masud. 2012. On the Termination of Integer Loops. ACM Transactions on Programming Languages and Systems 34, 4, Article 16 (December 2012), 24 pages. doi:10.1145/2400676.2400679