Addition Automaton
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≤t≤T, 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≤t≤T, 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):
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.
External resources
- Implementation in Jelly (with debug output and lax loop detection); runnable online at Try It Online!
- More context on what lead to the creation of Addition Automaton can be found in two Code Golf Stack Exchange posts, here and here.