Linear-Inequality Affine Transformation Automata

Linear-Inequality Affine Transformation Automata (LIATA) are a model for computation based upon applying affine transformations to vectors based on cases defined by linear inequalities. They are a generalization of the rules for BMO1 and were proven to be Turing complete.

Example

An example of a LIATA are the rules for BMO1:

$$f(a,b)={\begin{cases}(a-b,4b+2)&{\text{if }}a>b\\(2a+1,b-a)&{\text{if }}a<b\\\end{cases}}$$

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-case LIATA. The 2 dimensions are the parameters a,b and the two cases are the a<b and a>b rows. For each case the parameters are transformed via an affine transformation.

Formal Definition

A n-dimension, k-case LIATA is a piecewise defined partial function $f:\mathbb {Z} ^{n}\to \mathbb {Z} ^{n}$:

$$f({\vec {x}})={\begin{cases}f_{0}({\vec {x}})&{\text{if }}C_{0}({\vec {x}})\\f_{1}({\vec {x}})&{\text{if }}C_{1}({\vec {x}})\\&\vdots \\f_{k-1}({\vec {x}})&{\text{if }}C_{k-1}({\vec {x}})\\\end{cases}}$$

Where each $f_{i}:\mathbb {Z} ^{n}\to \mathbb {Z} ^{n}$ is an affine function and each $C_{i}:\mathbb {Z} ^{n}\to \{T,F\}$ is a "linear inequality condition" (defined below) such that for all ${\vec {x}}$ at most one condition $C_{i}({\vec {x}})$ applies. If none of the conditions apply, we say that it halts on that configuration ${\vec {x}}$.

Let a linear inequality term be any equation of the form $g({\vec {x}})\sim c$ where $g:\mathbb {Z} ^{n}\to \mathbb {Z}$ is a linear function and ~ is replaced by any (in)equality relation (=,<,≤,>,≥). Then let a linear inequality condition be any combination of linear inequality terms using logical AND, OR and NOT operations.

So, for example, the following are all linear inequality conditions:

• $a<b$ represented formally as $a-b<0$
• $3a\leq b<4a$ represented formally as $(b-3a\geq 0)\land (4a-b>0)$
• $a=2$ (note that we allow equalities as well)

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

See Also

• @Bard's proof that 3-dim LIATA are Turing complete: Discord link
• @star's proof that 2-dim LIATA are Turing complete: Discord link