Addition Automaton is an esoteric programming language developed/discovered by User:ais523 in 2023, after a study into how useful base-conversion operators would be for implementing Turing tarpits. It is quite similar to a one-dimensional cellular automaton (it is easy to compile between an addition and cellular automaton in either direction, although typically with a large increase in size).

The language comes in a few different "halt flavours"; these are identical except for their halting behaviour, which differs from flavour to flavour (but programs will behave identically up until the point that they halt).

## Specification

Each Addition Automaton program is designed for a specific numeric base b (an integer that's 2 or greater). The program consists of a transition table, which maps each of the b possible digits to a non-negative integer, and an initial value, which is a non-negative integer. A program must map the digit 0 to the integer 0; a program that does not do this is syntactically incorrect (implementations may diagnose this error, or if they prefer may react with undefined behaviour).

Execution of the program is based around a state value, a non-negative integer (whose initial value is specified by the program). An implementation repeatedly performs the following steps, until the program halts:

• Disassembly: The state value is expressed as a list of digits in base b.
• Transition: For each digit in the resulting list, replace that digit with the integer it is mapped to in the transition table.
• Reassembly: Multiply each integer in the resulting list by the appropriate power of b, so that it has the same place value that it had originally (i.e. if a digit d originally came from the bx position of the number and thus had a value of d×bx, and the transition gave it a new value v, calculate v×bx). Then add all those products together to form a new state value.

An alternative, less formal, way to think about this operation is that you are doing a "find and replace" operation on the digits of the state value in base b, but the replacements are arbitrary non-negative integers and thus could be more than one digit long (which causes them to carry into the more significant digits).

There are multiple flavours of the language, each of which has different rules for when it halts. Any given implementation should implement exactly one of these (for a given set of command-line options), and document which:

Lax loop detection
The program halts if the current state value is exactly equal to a power of b multiplied by any previous state value. (If this situation occurs, the program is necessarily in an infinite loop.)
Strict loop detection
The program halts if the current state value is exactly equal to any previous state value.
Halt-on-zero
The program halts if the state value becomes zero.
No halting
The program runs forever, and inspection of its internal state is needed to know whether it "should have halted".

It should be noted that multiplying the internal state value by a power of b never has any influence on the program's future behaviour (except when using strict loop detection) – the "trailing zeroes" map to themselves and thus have no influence on the rest of the program. Likewise, if the internal state is divisible by b or a power of it, it is possible to remove those trailing zeroes. As such, optimizing implementations may want to remove trailing zeroes in order to save memory (which is part of the reason why lax loop detection is a permitted halting flavour – loop detection is useful, but strict loop detection could block the optimization).

## Computational class

### Arbitrary b

If arbitrary values of b are allowed, Addition Automaton is trivially Turing complete, being able to fairly directly implement a wide range of languages. In fact, it is possible to almost directly implement a Turing machine itself; for a Turing machine with T states and S symbols, let b be S(T+1), and use a 1-based numbering of the Turing machine states but a 0-based numbering of the symbols. The transition table is designed as follows:

• For digits s less than S, map them to bs. (This maps 0 to 0, as required.)
• Other digits are of the form St+s (with 1≤tT, 0≤s<S). Consider which way the Turing machine moves when reading s in state t, and the resulting symbol s' and state t':
• If the Turing machine moves to the left, map St+s to St'b2+s'b.
• If the Turing machine moves to the right, map St+s to St' + s'b.

The encoding of the state value (and thus initial value) is to use a digit 0≤s<S to represent a tape element with symbol s that does not currently hold the Turing machine head, and a digit St+s (with 1≤tT, 0≤s<S) to represent a tape head in state t reading symbol s. The digits of the state value thus represent the tape of the Turing machine, although it moves one place-value in the more significant direction every iteration (ensuring among other things that the Turing machine never runs out of tape).

When using lax loop detection, state 0 can be used as a halt state. For strict loop detection, the Turing machine can halt by first deleting all the symbols on the tape, and then moving to the right in an infinite loop. For halt-on-zero, the Turing machine must halt by first deleting all symbols on the tape, and only then changing to state 0.

### Small values of b

Addition Automaton is also Turing-complete with some fairly small values of b. The smallest value is not currently known, and probably depends on the halting flavour in use.

One approach for writing Addition Automaton with small b is to emulate a cellular automaton. For example, the version of rule 110 that starts from a finitely initialised tape can be implemented with b=8 (using a transition table for which all elements are either 0 or 4218). However, that version of the cellular automaton is not Turing-complete; to be Turing-complete, rule 110 requires memory to be initialized with an infinitely repeating pattern, a finite section, and then a different infinitely repeating pattern. It is actually possible to implement this in Addition Automaton, via using a couple of digits (one for each side) to lazily initialize memory before the repeating pattern there is disturbed, but doing that requires b=10. Additionally, when doing this, there is no way for the Addition Automaton to recognise rule 110's halt state.

b=10 is, however, known to be possible (when using lax loop detection) via using a different approach; it is possible to compile Echo Tag into Addition Automaton (with a transition table that depends only on the value of n – the Echo Tag productions are specified using the initial string rather than being part of the transition table). 2-Echo Tag can be implemented with the following transition table:

Digit Maps to
1 10000
2 2
3 200000400
4 0
5 2020202000
6 600
7 620
8 1600
9 620

The value of n affects cases 3 and 5; increasing n by one adds another four `0`s between the `2` and `4` in case 3, and another `2020` in case 5.

The basic idea is for the Echo Tag productions to be represented as `1`s and `2`s that bounce around between a pair of `6`s, which creates the cycle needed for cyclic tag. Each production is represented using a pair of consecutive positions that might have or might not have a `1`/`2`; a 1 is represented by both being absent, and a 0 by the position that hits the `6` earlier being absent but the position that hits the `6` later being present. The data queue is also represented using `2`s; a 1 in the data queue is `2020` and a 0 is just zeroes. The data queue and productions hit a `6` simultaneously from opposite sides; when the production has a 1, the `2020` from the data queue will bounce off the `6` just like the `2`s in the productions do, and become `0101`; when the production has a 0, the second `2` will get deleted because the rule for `9` is the same as the rule for `7`, so it will just become `0100`. Towards the most significant end of the data queue is a `2` whose place-value has a different parity than the others, which serves to append to the end of the queue when it gets hit by a `1` (and thus becomes a `3`); when it gets hit it will move to a more significant position, leaving behind zeroes (effectively enqueueing n 0s to the end of the Echo Tag queue). However, it will also leave behind a `4` for one cycle. If the production contained a 1 (and thus the `3` was hit by an `0101` rather than an `0100`), this `4` will get hit by the second `1` and become a `5`, which changes values added to the data queue from being 0s to being 1s. Otherwise, the `4` deletes itself on the next cycle and leaves the 0s in place.

Here's an example of how this particular transition table behaves, implementing the 2-Echo Tag program [1,1,1,0] with a starting data queue of [1,1]. (For readability, trailing zeroes are removed, and the number is expressed in little-endian decimal so that the productions, on the left-hand side here, do not move around):

```60000028022202
600020083202
602000085200002
8000000812022202
61000008123202
60010008125200002
600001081212022202
6000000912123202
6000002802125200002
60002008120212022202
602000081212023202
800000081212124200002
6100000812121210002
60010008121210103
60000108121010105000002
600000091010101012022202
6000002600101012123202
6000200600001212125200002
60200006000202121212022202
800000060202020212123202
610000080202020202125200002
6001000812020202020212022202
60000108121202020202023202
60000009121212020202024200002
600000280212121202020200002
6000200812021212120200002
60200008121202121210002
800000081212120210103
610000081212121000105000002
6001000812121010100012022202
60000108121010101012023202
60000009101010101212124200002
600000260010101212121210002
6000200600001212121210103
6020000600020212121010105000002
80000006020202021010101012022202
610000080202020000101012123202
600100081202000000001212125200002
6000010812100000000202121212022202
60000009101010000202020212123202
60000026001010120202020202125200002
600020060000121212020202020212022202
6020000600020212121202020202023202
8000000602020202121212020202024200002
61000008020202020212121202020200002
600100081202020202021212120200002
6000010812120202020202121210002
60000009121212020202020210103
60000028021212120202020000105000002
600020081202121212020000000012022202
6020000812120212121000000002023202
8000000812121202101010000202024200002
61000008121212100010101202020200002
600100081212101010001212120200002
6000010812101010101202121210002
60000009101010101212120210103
60000026001010121212121000105000002
600020060000121212121010100012022202
6020000600020212121010101012023202
8000000602020202101010101212124200002
etc. (this program does not halt)
```

The easiest way to spot the correspondence is to look for 4s and 5s: a 4 appears when the Echo Tag program pushes a block of 0s onto the end of the data queue, and a 5 when it pushes a block of 1s.