The Exasperation Machine

The Exasperation Machine (TEM) is an esoteric programming language and a computational model created by User:Rainwave in 2026. The language can be seen as a brainfuck dialect that ditches explicit control flow in favor of an implicit loop and fallible movement instructions. It can also be seen as 1-dimensional A Painter Ant, but it has both conditional and unconditional move instructions.

The language provides an easy reduction target for other minimal languages, especially ones that have an implicit loop. In fact, it was originally created to serve as an intermediate step in A Painter Ant's Turing completeness proof.

Language Semantics

The Exasperation Machine operates on a bidirectionally unbounded tape. Each cell in the tape stores a single bit (either 0 or 1). Initially, every cell is set to 0.

A tape head is initially positioned on the first cell. The tape head can be controlled to move left/right and read/write the value of its current cell. The Exasperation Machine provides the following instruction set:

Instruction	Description
>	Move the tape head right to the next cell.
<	Move the tape head left to the previous cell.
/	Move the tape head right if the value of the current cell is 1. Otherwise, this instruction has no effect.
\	Move the tape head left if the value of the current cell is 1. Otherwise, this instruction has no effect.
1	Set the value of the cell under the tape head to 1.
0	Set the value of the cell under the tape head to 0.

The entire program is wrapped in an endless implicit loop. What this means is that the execution wraps around to the first instruction after the last instruction is executed.

A TEM program is written as a single string consisting of instructions. Implementations may ignore symbols that are not listed as instructions.

Computational class

The Exasperation Machine is Turing complete as any binary Turing machine can be compiled into it. One possible compilation strategy follows.

Turing machine

A Turing machine has a transition table where each row of the table contains a transition lookup rule when a particular state is active. Each rule usually reads like "For state $S$, if read $0$ then write $U$, move $V$, and change state to $W$. If read 1, then write $X$, move $Y$, and change state to $Z$." These rules can be broken down into three simpler primitive rules:

1. If state is $S$, then write $B$ and change state to $T$.
2. If state is $S$ and read $B$, then change state to $T$.
3. If state is $S$, then move $D$ and change state to $T$.

Like the standard Turing machine, we can construct these rules so that only one rule's condition is met when all rules are evaluated simultaneously. It can be shown that we need no more than 5 microstates for each TM transition rule. Therefore, we need $5n$ microstates in total to simulate a Turing machine with $n$ states.

The idea now is to compile each of these primitives into a reusable template of TEM instructions. We will use the following layout to encode the Turing machine. Each TM cell will be mapped to a contiguous block of TEM cells starting from [b][_][_] up to [b'][_][_].

...[b][_][_][s1][_][_][s2][_][_]...[s5n][_][_][b'][_][_][b][_][_][s1][_][_][s2][_][_]...[s5n][_][_][b'][_][_]...

Note:

• [b] (bit) stores the actual value of the TM cells. We want to normalize the tape head position to this cell at the start of each TM cycle.
• [s1] through [s5n] (states) encode a hot-bit for the current active microstate. Across the tape, only one of these can equal 1 at the start of each TM cycle.
• [_] are buffer cells. They should all equal 0 at the start of each TM cycle.
• [b'] stores a temporary copy of the value of [b]. This should be 0 when unused.

Rule 1

The first rule is the easiest to construct. The idea is that \> will shift the head alignment when the state $S$ is not active, causing subsequent writes to happen to buffer cells. After writing to [b] and [sT] (or their buffers), we then fix the alignment to +1 while simultaneously writing 0 to [sS] using /<0>. At the end, we use the +1 alignment to clear [b] and [sT]'s buffers.

>>>>>>...>>>               S times
\>
<<<<<<...<<<               S times
1                          1 or 0 depending on B
>>>>>>...>>>               T times
1
<<<<<<...<<<               T-S times. Use >>> if T is less than S
/<0>
<<<<<<...<<<               S times
0
>>>>>>...>>>               T times
0<
<<<<<<...<<<               T times

Rule 2

Rule 2 is conceptually similar to rule 1. The difference is that there are two conditions that need to be satisfied, resulting in three possible alignment offsets.

>>>>>>...>>>                S times
\>
<<<<<<...<<<                S times
\>                          If B=1. Use / if B=0
>>>>>>...>>>                T times
1
<<<<<<...<<<                T times
</>                         If B=1. Use / if B=0
>>>>>>...>>>                S times
/</                         If B=1. Use / if B=0
>>>>>>...>>>                T-S times. Use <<< if T is less than S
0>0<<\>
<<<<<<...<<<                T-S times. Use >>> if T is less than S
0
>>>>>>...>>>                T-S times. Use <<< if T is less than S
/<
<<<<<<...<<<                T times

Rule 3

Rule 3 is the trickiest one to construct. For now, let's consider the case where $D={\text{Left}}$.

We need to move [b] to [b'] and [sS] to the previous block's [sT]. If state $S$ was active, the result is that the cells between [sS] and the previous block's [sT] will be devoid of 1's. We can then use a sequence of \> instructions to produce a $15n+6$ (a full block length) cell discrepancy between the cases where state $T$ ends up active and inactive. At the end, we restore the value of [b].

\>
>>>>>>...>>>                5n+1 times
1
<<<<<<...<<<                5n+1 times
/<0>
>>>>>>...>>>                5n+1 times
0<
<<<<<<...<<<                5n+1-S times
\>
<<<<<<...<<<                5n+2+S-T times
1
>>>>>>...>>>                5n+2+S-T times
/<0>
<<<<<<...<<<                5n+2+S-T times
0<
\>\>\>...\>                 15n+6 times
>>>>>>...>>>                10n+3-T times
\>
<<<<<<...<<<                5n+1 times
1
>>>>>>...>>>                5n+1 times
/<0>
<<<<<<...<<<                5n+1 times
0<<<<\>
<<<<<<...<<<                5n+1 times
1
>>>>>>...>>>                5n+1 times
/<0>
<<<<<<...<<<                5n+1 times
0<

The case where $D={\text{Right}}$ can be constructed in a similar manner. It is therefore left as an exercise for the reader.

Implementations

Python

import itertools, collections
tape = collections.defaultdict(int)
p = 0
for c in itertools.cycle(input()):
    if c in '/\\' and tape[p] or c in '><':
        p += {'>': 1, '<': -1, '/': 1, '\\': -1}[c]
    elif c in '10':
        tape[p] = int(c)

JavaScript

This implementation can be run inside a JS runtime or a web console

const code = "" // write your code here
let tape = {}
let i = 0, p = 0
while (true) {
    const c = code[i++ % code.length]
    if ("/\\".includes(c) && tape[p] || "><".includes(c))
        p += { '>': 1, '<': -1, '/': 1, '\\': -1 }[c]
    else if ("10".includes(c))
        tape[p] = Number.parseInt(c)
}

Rust

fn main() {
    let mut code = String::new();
    std::io::stdin().read_line(&mut code).unwrap();
    let mut p: i32 = 0;
    let mut tape = std::collections::HashSet::<i32>::new();
    for c in code.chars().cycle() {
        match c {
            '>' => p += 1,
            '<' => p -= 1,
            '/' => if tape.contains(&p) {
                p += 1
            }
            '\\' => if tape.contains(&p) {
                p -= 1
            }
            '1' => {
                tape.insert(p);
            }
            '0' => {
                tape.remove(&p);
            }
            _ => (),
        }
    }
}

Further simplifications

The Exasperation Machine is Turing complete even when restricted to a unidirectionally unbounded tape. However, this causes < instructions and successful \ instructions to result in undefined behavior if executed when the tape head is at the leftmost cell.

General Exasperation Machine

The General Exasperation Machine (GEM) is a superset of TEM. Instead of storing a single bit, each cell can store arbitrarily many bits. The machine should be able to inspect and mutate any individual bit, which means the instructions need to take an argument to determine which bit to inspect/mutate. One upside of this generalization is that the > and < instructions become redundant, reducing the instruction count to just 4. It's easy to see that 2 bits per cell is the minimum requirement for a GEM without > and < to be Turing complete.

See also

• A Painter Ant
• Stun Step