We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
Backstroke
Backstroke is a reversible programming language where the only operation available to a program is to rearrange its own existing instructions. It is one of the most restricted members of a general family of languages that were investigated by User:ImOnlyHereForReversibleComputing as early as 2024, but was first posted in October 2026.
Language overview
A Backstroke program consists of a sequence of instructions. Each instruction specifies a local permutation to be applied to the neighborhood of instructions around that instruction's current location. For example, an instruction might swap the two instructions to its right, or it might move the instruction from two spaces to its left to be directly to its right. Each instruction is written as a permutation array with a single element of the array surrounded by parentheses. The parenthesized element represents the instruction's own position within the neighborhood of instructions being permuted. For example, an instruction that swaps the two elements to its right without moving itself would be written as:
[(0) 2 1]
An instruction that mirrors the entire 5-element neighborhood surrounding itself might be written as:
[4 3 (2) 1 0]
In both of these examples, the current instruction does not move within the neighborhood as part of the permutation; however, it is possible for the instruction to move itself. In these situations, the index within the parentheses and the position of the parentheses will not agree. When the two disagree, the position of the parenthesized element specifies the final position of the current instruction within the neighborhood, whereas the index inside of the parentheses specifies the initial position of the current instruction within the neighborhood.
For example, an instruction that shifts the two elements from its left to be to its right would be written as:
[(2) 0 1]
This instruction effectively moves itself two spaces to the left.
When the current instruction moves during a permutation, the instruction pointer follows it. Instructions that move themselves to the left are critical for computation, because this is the only method available within the language for looping.
The general execution process of the language involves alternately:
- Applying the local permutation of the current instruction, following it if it moves.
- Moving to the next instruction to the right.
Before a program is executed, an infinite number of "nop" instructions, which do nothing and can be written as [(0)], are prepended to the start of the program and appended to the end of the program. Execution of the program starts with evaluating the first instruction specified in the program source, skipping the preceding infinite nops. The program halts when the current instruction is a nop and all instructions that follow are also nops, as, in this situation, no computation would ever occur again.
Reversibility
Each Backstroke instruction has a unique inverse, which can be computed by the following steps:
- Record which number is inside of the parentheses from the initial instruction.
- Compute the permutation array for the inverse permutation of the permutation represented by the initial instruction.
- Wrap parentheses around the element that occupies the position indexed by the number inside the parentheses from the initial instruction.
So, each instruction is guaranteed to be reversible.
The execution of a program consists of alternately applying an instruction, which is reversible, and moving to the next instruction to the right, which is also reversible (by moving to the next instruction to the left). As a result, the entire language is reversible.
Examples
Infinite loop
In order to maintain reversibility, reversible programming languages generally have to maintain some kind of "loop counter" when they enter an infinite loop, unless the program exists within an implicit loop. Since Backstroke does not run in an implicit loop, it requires a counter. Although the values of instructions cannot be modified, the distances between them can, and programs in the language can use the distances between known instructions to encode the values of counters. One of the simplest infinite looping programs is:
[1 (0)] [1 (2) 3 0] [1 (2) 3 0]
To demonstrate the execution of this program, we can assign names to these instructions for readability. We can assign A = [1 (0)], and B = [1 (2) 3 0], and represent the background nops as single digit numbers that repeat every 10 places to make the movement through the instruction list easier to read. To help make neighborhoods clear, we will surround the neighborhood of the instruction being applied with curly braces ({}). With this, the execution of the loop looks like:
... 7 8 9 0{A B}B 1 2 3 4 5 6 ...
^ apply:
... 7 8 9 0{B A}B 1 2 3 4 5 6 ...
^ move right:
... 7 8 9 0{B A B 1}2 3 4 5 6 ...
^ apply:
... 7 8 9 0{A B 1 B}2 3 4 5 6 ...
^ move right:
... 7 8 9 0 A B{1}B 2 3 4 5 6 ...
^ apply (does nothing):
... 7 8 9 0 A B{1}B 2 3 4 5 6 ...
^ move right:
... 7 8 9 0 A{B 1 B 2}3 4 5 6 ...
^ apply:
... 7 8 9 0 A{1 B 2 B}3 4 5 6 ...
^ move right:
... 7 8 9 0 A 1 B{2}B 3 4 5 6 ...
^ apply (does nothing):
... 7 8 9 0 A 1 B{2}B 3 4 5 6 ...
^ move right:
... 7 8 9 0 A 1{B 2 B 3}4 5 6 ...
^ apply:
... 7 8 9 0 A 1{2 B 3 B}4 5 6 ...
^ etc...
Since there is always a non-nop instruction at or to the right of the instruction pointer, this program will run forever without halting. The first instruction that executes, which arranges the other two instructions to enable the loop, is left behind, and the distance from the instruction pointer to that left-behind instruction encodes the loop counter.
Implementation of reversible logical circuits
Backstroke is capable of implementing arbitrary reversible circuits. Consider the following encoding of booleans as instructions:
| Boolean | Instruction |
|---|---|
false
|
[(0)]
|
true
|
[(0) 1 3 2]
|
The choice of having true swap the second and third elements to the right, rather than the first and second elements to the right, was done so that it would be possible to apply a boolean instruction to its arguments without having to immediately execute one of the arguments afterward; instead, an additional instruction can be inserted which arranges the output values to set up the next gate of the circuit.
When we execute a "boolean" instruction, we perform a conditional swap on two other instructions, conditional on the truth value of the boolean. This means that executing a boolean effectively implements a "controlled swap" or "Fredkin" gate, which is a universal gate for population-preserving reversible circuits. Because the inputs and the outputs of the Fredkin gate will always be at predictable offsets, it is trivial to design a sequence of instructions that will apply an arbitrary sequence of Fredkin gates to a collection of booleans, and then arrange those booleans back into their original order.
If we use a "dual-rail logic" encoding of bits (where each bit is represented by a true/false pair, with their relative order determining the truth value), then Fredkin can be used to directly implement both dual-rail Fredkin and dual-rail CNOT, which makes it universal over non-population-preserving dual-rail reversible circuits as well.
Swimmers
"Swimmers" are small structures which travel in one direction through the instruction list, stepping with a particular stride until they find a true instruction. When they find it, they either pull it one stride closer or push it one stride further away, then switch to a different set of instructions to start traveling back through the instruction list in the opposite direction. Here, we will give examples of two swimmers that move to the right with a stride of 2, then turn around and return to the left with a stride of 2. One pushes the first true it finds to the right by 2, the other pulls the first true it finds to the left by 2.
This kind of swimmer travels to the right 2 spaces at a time, pushes the first true it finds 2 spaces to the right, then turns around and travels to the left 2 spaces at a time:
[1 8 (5) 9 2 3 4 0 6 7] X [(0) 2 1] [9 8 1 10 6 11 2 4 (3) 7 0 5] [1 (0)] [1 8 (5) 9 2 3 4 0 6 7] [(7) 0 4 5 6 2 8 9 1 3] [(7) 0 4 5 6 2 8 9 1 3]
Here, the X represents an instruction that is not part of the swimmer itself. This is the instruction that has been read-in and is being "tested" as the swimmer moves through the instruction list. Similar to the infinite loop example above, the initial value of X will be the instruction that prepares the swimmer for launch, because the swimmer actually needs to begin executing from its inner instructions rather than its first instruction.
We can assign some identifiers here, to make this a little more readable:
A = [1 8 (5) 9 2 3 4 0 6 7] B = [(7) 0 4 5 6 2 8 9 1 3] C = [(0) 2 1] D = [9 8 1 10 6 11 2 4 (3) 7 0 5] E = [1 (0)]
With this, we can write our swimmer as:
A X C D E A B B
The A terms here are similar to the infinite loop example above, but they are extended to also drag along a sequence of interior instructions, C D E, that are used to test the value of each X, and also drag along B B, which are the pair of alternate looping instructions that the swimmer switches to in order to swim back in the opposite direction. D triggers the turn-around, but normally, C will swap D and E, moving D out of the way before it executes. However, if X happens to be a true, then it will also swap D and E, and the two swaps will cancel, allowing D to finally execute and initiate the direction change.
When the X being tested is false the swimmer will behave as follows:
... 9 A{F}C D E A B B 1 2 3 4 5 ...
^ apply (does nothing):
... 9 A{F}C D E A B B 1 2 3 4 5 ...
^ move right:
... 9 A F{C D E}A B B 1 2 3 4 5 ...
^ apply:
... 9 A F{C E D}A B B 1 2 3 4 5 ...
^ move right:
... 9 A F C{E D}A B B 1 2 3 4 5 ...
^ apply:
... 9 A F C{D E}A B B 1 2 3 4 5 ...
^ move right:
... 9{A F C D E A B B 1 2}3 4 5 ...
^ apply:
... 9{F 1 A 2 C D E A B B}3 4 5 ...
^ move right:
... 9 F 1 A 2 C D E A B B 3 4 5 ...
^ now in position to test the next instruction 2 steps to the right...
When the X being tested is true the swimmer will behave as follows:
... 9 A{T C D E}A B B 1 2 3 4 5 ...
^ apply:
... 9 A{T C E D}A B B 1 2 3 4 5 ...
^ move right:
... 9 A T{C E D}A B B 1 2 3 4 5 ...
^ apply:
... 9 A T{C D E}A B B 1 2 3 4 5 ...
^ move right:
... 9{A T C D E A B B 1 2 3 4}5 ...
^ apply:
... 9{2 1 T 3 B 4 C E D B A A}5 ...
^ move right:
... 9 2 1{T 3 B 4 C E D B A A}5 ...
^ apply:
... 9 2 1{B T C E D B A A 3 4}5 ...
^ move right:
... 9 2 1 B{T C E D}B A A 3 4 5 ...
^ apply:
... 9 2 1 B{T C D E}B A A 3 4 5 ...
^ move right:
... 9 2 1 B T{C D E}B A A 3 4 5 ...
^ apply:
... 9 2 1 B T{C E D}B A A 3 4 5 ...
^ move right:
... 9 2 1 B T C{E D}B A A 3 4 5 ...
^ apply:
... 9 2 1 B T C{D E}B A A 3 4 5 ...
^ move right:
... 9{2 1 B T C D E B A A}3 4 5 ...
^ apply:
... 9{B 2 C D E B A A 1 T}3 4 5 ...
^ move right:
... 9 B 2 C D E B A A 1 T 3 4 5 ...
^ now in position to test the next instruction 2 steps to the left...
It's important for the functionality of this structure that while the swimmer pushes the true to the right, it also jumps even further to the right itself, so that its next step will be to test the true again. This second test is needed to swap the D back out of the path of execution again. It's also important that the swimmer does not disturb the order of the instructions it skips over. This allows for data to be stored in multiple separate interleaved data "channels" that swimmers can read and modify individually.
We can also define the variant swimmer that travels in exactly the same manner, but pulls the true closer to the left instead of pushing it further to the right:
[1 8 (5) 9 2 3 4 0 6 7] X [(0) 2 1] [3 1 8 0 4 6 (5) 9 2 7] [1 (0)] [1 8 (5) 9 2 3 4 0 6 7] [(7) 0 4 5 6 2 8 9 1 3] [(7) 0 4 5 6 2 8 9 1 3]
These two differ only in their fourth instruction, which determines whether the true is pushed or pulled.
For simplicity of implementation, these swimmers are constructed in such a way that they are only guaranteed to function correctly when they encounter a true while moving to the right. It is likely possible to build a swimmer that works correctly in both directions, but it would likely be more complex.
For some of the discussions below, it's valuable to be aware that mechanism used to identify the true is just to execute it and see what happens. This means that, rather than pushing instructions, swimmers can technically be used to activate literally any subprocedure of the program, by substituting any arbitrary instruction into their path. This fact can be exploited to intercept them on their return trajectory.
Computational class
Because it can use distances to encode counters, move the instruction pointer to the left in order to loop, and can represent arbitrary logical circuits for evaluating program logic, Backstroke is Turing complete, as this featureset can be used to implement the unbounded, unsigned 4-cell variant of Reversible Brainfuck, although the most straightforward translation requires some instructions with very large neighborhoods, of sizes that are determined by the length of the program. A general sketch of the implementation will be provided here.
A program encoding consists of a few parts:
- A collection of "booleans" (as described above) representing a one-hot encoding of the instruction pointer; there is one boolean per instruction in the corresponding Reversible Brainfuck program, plus additional "start" and "end" instruction pointer positions representing the positions before the first instruction and after the last instruction. Exactly one of the booleans is
truewhile the others are allfalse. Initially, the boolean corresponding to the program start istrue. - A sequence of instruction pairs each acting as the trigger for a different side effect (shift left, shift right, increment, decrement, or do nothing).
- Four infinite interleaved "channels" of booleans, each containing exactly one
true, each at a distance representing the numerical value of one counter. These channels lie off the end of the main program, extending into the infinite nops that are appended to the end of the program. There is a specific position in each channel called the "zero position", and thetruewill be located at that position if the counter is equal to zero. - The material for constructing either a push swimmer or a pull swimmer, along with a harness for intercepting a returning swimmer and resuming the program loop.
- A logical circuit which uses the one-hot encoded instruction pointer to swap (or not swap) one of the side effects pairs with the "do nothing" side effect pair.
- A logical circuit which uses the one-hot encoded instruction pointer and the boolean at the zero position of the current counter to compute a new one-hot encoded instruction pointer.
- A scaffolding around the entire encoding that aids it in executing it in a loop that cycles through the five phases of execution: check for termination, compute side effect decision, apply side effect, uncompute side effect decision, and move to next instruction.
Side effects
Each side effect is encoded as a pair of "setup" and "teardown" instructions. When a side effect is to be executed, first, a circuit will be used to swap that side effect pair into the place of the "do nothing" side effect, so that all side effects can be executed from a known location. In order to execute the side effect, a follow-up instruction is loaded in the position immediately after the default position of the "teardown" for the "do nothing" side effect, then the current instruction moves itself to the position immediately before the "setup" instruction for the "do nothing" side effect. The side effect setup executes, and this is expected to execute a subroutine that performs the side effect. When the subroutine completes, the core structure of the program is expected to have been reverted to its state before the side effect was performed (aside from any side effects on the counter channels), and the last instruction to execute must be the "teardown" instruction, which must move itself into the position immediately preceding the follow-up instruction. The follow-up instruction then executes to move to the next phase of execution.
Side effect encodings
The "do nothing" side effect, which would be used for pure control flow instructions, does nothing. It uses a nop for both its setup and teardown steps.
The "shift left" and "shift right" side effects shift the entire program by 1 space to modify its relative offset to the counter channels, changing which is the "current counter". Shifting right involves taking a single instruction from the region in between the program and the counter channels and moving it to the other side of the program, moving the program and the channels one space closer together. The exact inverse effect, grabbing an instruction from before the start of the program and inserting it between the program and the channels, can be used to left shift. These instructions are the setup steps for these side effects, and they each have a nop for their teardown step. The total size of the program (excluding the unbounded channels) can be determined in advance, so it's always possible to devise appropriate instructions for this, though the instructions themselves may be enormous.
The "increment" and "decrement" side effects require a more complex subroutine that involves launching swimmers to push or pull the boolean instructions representing the heads of the counters being used by the program.
Swimmers
In order to implement the increment and decrement side effects, the interpreter uses push and pull swimmers with a stride of 4. This allows a swimmer to step through each element of a single counter's channel in the 4 interleaved channels off the end of the program.
The 4-stride push swimmer can be implemented as:
[1 8 9 10 (5) 11 2 3 4 0 6 7] X [(0) 2 1] [11 8 9 10 1 12 13 14 6 15 2 4 (3) 7 0 5] [1 (0)] [1 8 9 10 (5) 11 2 3 4 0 6 7] [(9) 0 6 7 8 4 10 11 1 2 3 5] [(9) 0 6 7 8 4 10 11 1 2 3 5]
The 4-stride pull swimmer can be implemented as:
[1 8 9 10 (5) 11 2 3 4 0 6 7] X [(0) 2 1] [5 1 2 3 10 0 6 8 (7) 11 4 9] [1 (0)] [1 8 9 10 (5) 11 2 3 4 0 6 7] [(9) 0 6 7 8 4 10 11 1 2 3 5] [(9) 0 6 7 8 4 10 11 1 2 3 5]
Both of these follow the same general A X C D E A B B structure from the swimmers discussed in a previous section, but have been modified with larger neighborhoods to increase their strides.
The components needed for building push and pull swimmers will be located at a fixed offset within the program where the increment and decrement setup can access them. These parts include the pairs of right-moving and left-moving loop instructions, as well as the interior direction switching instructions needed for both kinds of swimmers, and a new 3-cycling instruction needed for intercepting the swimmer on its return trajectory. We can write this 3-cycling instruction as:
Z = [4 1 2 3 8 5 6 7 0 9 10 11 12 (13)]
You can see that there is a 3-cycle in here cycling the elements at indexes 0, 4, and 8 within the neighborhood.
If we name our side effect setup instruction S and our side effect teardown instruction T, as well as using the A, B, C, D and E names from the previous swimmer explanation, our setup instruction needs to create the following arrangement in-between the program and the counter channels, aligned with the current counter channel:
... 0 1 2 3 T 5 6 7 A S C D E A B B 9 0 1 Z 2 ...
As in previous sections, the digits represent nops. Because it is the S instruction constructing this arrangement, the structure begins executing at the instruction immediately following the S, the C. The Z instruction will be tested once on the way to the right and once on the way back, and this will result in the three-cycle being applied twice, shifting T into the position previously occupied by S by the time that position is tested again. This will trigger the teardown logic, which will take all of the swimmer components, which will be at known locations, and put them back into their original places, then move to the next phase of interpretation.
Side effect swapping circuit
The side effect swapping circuit is used to compute (or uncompute) which side effect should be applied by a given instruction. For each one-hot encoded instruction pointer boolean that corresponds to a non-control flow instruction in the Reversible Brainfuck program, that boolean is used to conditionally swap both the setup and teardown for that instruction's side effect with the setup and teardown for the "do nothing" side effect. Since at most one of the one-hot instruction pointer booleans will be true, at most one swap will occur. This circuit is used both to swap the side effect to be performed into a known location (the "do nothing" side effect's starting place) before executing it, but also to swap the executed side effect back to its original position after it is executed. Since the side effect swapping circuit is conditional only on the instruction pointer position, and the instruction pointer position cannot be changed by any side effects, this cleanup is guaranteed to complete predictably.
Control flow
One-hot instruction pointer
Rather than using some kind of counter to encode the Reversible Brainfuck instruction pointer, the instruction pointer is effectively encoded as a giant bitmask, where exactly one bit is set, with the index of the set bit being the index of the corresponding instruction in the Reversible Brainfuck program. This "one-hot" encoding allows the instruction pointer to be used in a directly conditional way without any kind of decoder or comparison; you can check if the instruction pointer equals a particular value by extracting the boolean at that index and applying it to conditionally swap two values.
Next instruction pointer circuit
The instruction pointer advances using a circuit that picks a new position in the one-hot encoding to place the true value. This circuit consists of two parts.
The first part is a sort of "ghost leg lottery" that just performs a sequence of swaps over the one-hot encoding, applying a fixed permutation that maps each boolean to a fixed new position. Since it is effectively a single fixed permutation, this ghost leg lottery portion can also be encoded as a single giant instruction. This handles cases where the program unconditionally advances from one instruction to the next.
The second part is a sequence of controlled swaps, where the zero position boolean of the current counter is used to conditionally swap a collection of boolean pairs from the one-hot encoding. This handles conditional branching, corresponding to Reversible Brainfuck's [] instructions. Every one-hot boolean will be involved in at most one swap in this part.
After the instruction prior to a control flow instruction is executed, the ghost leg portion will move the instruction pointer onto the "starting brace", then the controlled swap portion will either move or not move the instruction pointer to the paired opposite brace. The brace will then "execute", which does nothing, then the ghost leg portion will run again, moving the instruction pointer off the brace and onto the next instruction following it.
Phases
The interpretation of the Reversible Brainfuck program goes through a cycle of phases. There are five phases of execution:
- Check for termination
- Compute side effect decision
- Apply side effect
- Uncompute side effect decision
- Move to next instruction
The execution of these phases is mediated by five "phase instructions". Each phase instruction has the responsibility of moving itself to the location preceding the next phase's procedure, moving the previous phase instruction to the end of the phase instruction collection, and moving the head of the phase instruction collection to the end position of the next phase's procedure.
Each phase has its own procedure, except for computing and uncomputing side effects, which use the same shared procedure (since they both consist of performing, at most, a single swap, running the same procedure a second time uncomputes the result of running it the first time).
Each of these procedures has been discussed already except the termination check.
Check for termination
The termination check applies special logic at the start and end of the program to initiate or break from the interpreter loop. Thus, it will always be both the first and the last phase executed by a program.
For simplicity, assume that the one hot instruction pointer booleans for the "program end" and the "first instruction" of the program will be stored inside of the termination check procedure. As long as they are stored at a known offset within the program, it doesn't matter where they are stored, so this doesn't inhibit the interpreter's ability to implement control flow, and it makes the behavior of the termination check easier to understand. If we stored them elsewhere, the termination check would just need some additional instructions to move these booleans into place, and then move them back to their original location. The first instruction of the Reversible Brainfuck interpreter will be an instruction J, which jumps into the middle of the termination check. After it jumps, the termination check procedure will look like this:
TERMINATION_CHECK_PHASE FIRST_INSTRUCTION_IP [(0) 2 1] [1 (0)] J PROGRAM_END_IP [(0) 2 1] HALT [1 (0)] COMPUTE_SIDE_EFFECT_PHASE
Here, TERMINATION_CHECK_PHASE and COMPUTE_SIDE_EFFECT_PHASE are the phase instructions for the current and next phases respectively. FIRST_INSTRUCTION_IP is the one-hot instruction pointer boolean for the first instruction of the program, and PROGRAM_END_IP is the one-hot instruction pointer boolean for the end of the program. HALT is an instruction that moves itself past the end of the program and into the counter channels, from which point the instruction pointer will travel past the ends of the counters and then halt. And J marks the location where our initial instruction jumps to.
The basic structure of the termination checks is similar to the structure of the swimmer's internal turnaround instructions. If we look at the HALT instruction, by default, it gets swapped out of the way by the preceding [(0) 2 1] instruction, and the [1 (0)] instruction executes instead, skipping over it. However, if PROGRAM_END_IP is true, it will also swap those two instructions, putting HALT in the execution path, and halting the program.
The instructions around J work exactly the same way, except that it initially jumps *into* the default path of execution. It relies on the fact that FIRST_INSTRUCTION_IP will be true the second time that the termination check is run, this time not to swap it into the path of execution, but instead to permanently swap it out of the path of execution.
This construction would run into issues if the first instruction of the Reversible Brainfuck program was [, because the first branch would always be taken before the termination check is run again, and the instruction pointer would never actually occupy the first instruction. However, if a Reversible Brainfuck program begins with a [, you can prefix the program with +- to force a non-control flow instruction to be the first instruction without changing its behavior.
Open problems
Finite universal instruction set
The above proof sketch of Turing completeness shows that Backstroke is Turing complete, but the method of encoding programs can include arbitrarily large instructions depending on the complexity of the program. Because the language is Turing complete, it must be possible to implement a universal interpreter, which means that there must exist a finite set of Turing complete instructions; however, no such set has been identified yet.
Some obvious approaches would be to either explicitly convert a universal interpreter written in Reversible Brainfuck to its equivalent Backstroke program according to the schema in the Turing completeness sketch, or to come up with a scheme for simulating programs containing arbitrary Backstroke instructions with a smaller set of instructions.
The "Dryland Backstroke" problem
"Dryland Backstroke" is a variant of Backstroke in which the infinite nops are not prepended and postpended to the program before it is executed, effectively limiting programs to a finite amount of "memory". If a program attempts to move an instruction that lies outside the bounds of the instruction sequence, it halts with an error. A Dryland Backstroke program only halts without an error if it successfully executes an instruction that becomes the last instruction of the program after it executes. The "Dryland Backstroke Problem" asks, for a given program length, what is the longest a program can possibly run before successfully halting without an error. This problem was initially considered as a method of searching for computationally-useful primitive instructions.
Because Dryland Backstroke programs effectively have access to a finite amount of memory, and because it is not possible for a program to return to its initial state (because there is no way to "move right" onto the left-most instruction of the program), all Dryland Backstroke programs must either encounter an error or successfully halt without an error in a finite amount of time. As a result, unlike the Busy Beaver Problem, this problem is decidable. Nonetheless, the time requirements of evaluating the problem through brute force methods grow extremely quickly and rapidly become intractable, as the number of candidate programs grows superexponentially. The number of candidate instructions appears to grow according to (N^2 - N + 1) * (N - 1)!(OEIS A001564), and the total number of candidate programs thus grows according to ((N^2 - N + 1) * (N - 1)!)^N.
| N | Candidate Instruction Count | Candidate Program Count |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 3 | 9 |
| 3 | 14 | 2,744 |
| 4 | 78 | 37,015,056 |
| 5 | 504 | 32,520,160,641,024 |
| 6 | 3,720 | 2,650,071,791,407,104,000,000 |
| 7 | 30,960 | 27,265,072,953,773,767,954,268,160,000,000 |
| 8 | 287,280 | 4.6392 x 10^43 |
The best known programs for smaller N are as follows:
| N | Best Lower Bound | Best Upper Bound | Best Known Operation Count | Best Known Program |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | [(0)]
|
| 2 | 3 | 3 | 3 | [(0)] [(1) 0]
|
| 3 | 7 | 7 | 7 | [(0)] [(1) 2 0] [(1) 0]
|
| 4 | 15 | 15 | 15 | [(0)] [(1) 3 0 2] [(1) 2 0] [(1) 0]
|
| 5 | 33 | 600 | 33 | [(0)] [(1) 0] [1 (2) 0] [2 (3) 1 0] [1 (4) 3 2 0]
|
| 6 | 39 | 4320 | 39 | [(0) 2 1] [(1) 0] [(0)] [(1) 2 0] [1 (2) 0] [(2) 0 1]
|
| 7 | 54 | 35280 | 54 | [(0) 2 1] [(1) 0] [(1) 2 0] [1 0 (2)] [(2) 0 1] [1 (2) 0] [(2) 0 1]
|
| 8 | 82 | 322560 | 82 | [1 (0)] [1 0 (2)] [(1) 2 0] [(0) 2 1] [1 (2) 0] [1 (2) 0] [(2) 0 1] [(2) 0 1]
|
Initially, there appears to be a pattern of 2^N - 1, but this is exceeded at N = 5. The N = 5 program is not known to be optimal, and the programs for N > 5 were identified by a more constrained search and are almost certainly very suboptimal.
The obvious lower bound of N is given by a program consisting of N copies of [(0)].
The upper bound of N * N! is given by assuming that the program will visit every possible state (every permutation of instructions with the instruction pointer at every possible location for each permutation). However, this is a vast overestimate for Ns that have been investigated. For N <= 4, all options have been explored through brute force search, so these programs are known to be optimal.