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{if }\overrightarrow{x}\in H_1\\ & ⋮\\ f_{p-1}(\overrightarrow{x})& \text{if }\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.

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