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.