Linear-Inequality Affine Transformation Automata

From BusyBeaverWiki
Jump to navigation Jump to search

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:

where is undefined. BMO1 halts iff there exists k such that is undefined (in other words 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 and 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 :

Where each is an affine function and each is a "linear inequality condition" (defined below) such that for all at most one condition applies. If none of the conditions apply to , we say that it halts on that configuration.

Let a linear inequality term be any equation of the form where 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:

  • represented formally as
  • represented formally as
  • (note that we allow equalities as well)

Given a LIATA f, we say that it halts in k steps starting from configuration iff is undefined.

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