Addition Automaton

From Esolang
Jump to navigation Jump to search

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).


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.
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 0s 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 1s and 2s that bounce around between a pair of 6s, 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 2s; 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 2s 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):

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.

External resources