Linear-Inequality Affine Transformation Automata

Note: This article is currently in flux as we investigate previous literature on the topic shared by @savask: https://discord.com/channels/960643023006490684/1239205785913790465/1422997913558323392

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.

Formal Definition

A n-dimension, k-case LIATA 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{if }{C}_0(\overrightarrow{x})\\ f_1(\overrightarrow{x})& \text{if }{C}_1(\overrightarrow{x})\\ & ⋮\\ f_{k-1}(\overrightarrow{x})& \text{if }{C}_{k-1}(\overrightarrow{x})\\ \end{array}$$Where each $f_i:{\mathbb{\mathbb{Z}}}^n\to {\mathbb{\mathbb{Z}}}^n$ is an affine function and each $C_i:{\mathbb{\mathbb{Z}}}^n\to \{T,F\}$ is a "linear inequality condition" (defined below) such that for all $\overrightarrow{x}$ at most one condition $C_i(\overrightarrow{x})$ applies. If none of the conditions apply to $\overrightarrow{x}$, we say that it halts on that configuration.

Let a linear inequality term be any equation of the form $g(\overrightarrow{x})\sim c$ where $g:{\mathbb{\mathbb{Z}}}^n\to \mathbb{\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\le b<4a$ represented formally as $(b-3a\ge 0)\wedge (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 $\overrightarrow{x}$ iff $f^k(\overrightarrow{x})$ is undefined.

Example

An example of a LIATA 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-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.

Turing Complete

LIATA are Turing complete. This has been proven by implementing Minsky machines as LIATA:

• @Bard's proved that 3-dim LIATA are Turing complete: Discord link
• @star's proved that 2-dim LIATA are Turing complete: Discord link
• In progress: Shawn Ligocki is working on a proof that 2-case LIATA are Turing complete: Discord link