REFRACTRAN

REFRACTRAN is a reversible variant of FRACTRAN, investigated by User:ImOnlyHereForReversibleComputing at least as early as June of 2024, but first posted in September of 2026. REFRACTRAN replaces FRACTRAN's repeated searches with a single continuous bidirectional search. This both makes the execution of the program reversible and also makes it function somewhat more like a conventional programming language.

Language Description

A REFRACTRAN program consists of a list of fractions, along with an initial integer value. When the program begins execution, it begins a forward search through the fraction list, starting on the first fraction.

While the program is performing a forward search, it performs the following steps repeatedly:

• It checks if the program state integer multiplied by the current fraction results in an integer value.
  • If it does result in an integer value, the program state integer is replaced with this value, then the program switches to a reverse search and proceeds to the previous fraction in the sequence.
  • If it does not result in an integer value, the search proceeds to the next fraction in the list and continues the forward search.

While the program is performing a reverse search, it performs the following steps repeatedly:

• It checks if the program state integer divided by the current fraction results in an integer value.
  • If it does result in an integer value, the program state integer is replaced with this value, then the program switches to a forward search and proceeds to the next fraction in the sequence.
  • If it does not result in an integer value, the search proceeds to the previous fraction in the list and continues the reverse search.

The program halts if the search goes beyond either end of the fraction list.

Similar to FRACTRAN, the underlying logic of programs generally involves treating the prime powers of the program state integer and the numerators and denominators of the fractions as being registers storing values. Each fraction then becomes an instruction that is conditionally executed if the prime powers in the program state integer are at least as large as those in the denominator (or, during a reverse search, the numerator) of the fraction being evaluated.

Syntax of Code Examples

The code examples on this page use a few conventions to make representing and explaining programs easier.

Rather than just being represented as the quotient of two raw integer literals, the examples will frequently represent the numerators and denominators of fractions each as being a product of multiple terms, with division binding with a lower operator precedence than multiplication. For example, rather than 15 / 77, an example might write this as 3 * 5 / 7 * 11, making it much easier to reason about the fractions in terms of their prime factors.

But, the examples also largely bypass using numeric literals entirely, and instead use a "prime placeholder" syntax. An identifier preceded by an at symbol (for example, @left_tape) is interpreted as a placeholder for a prime number. Each unique prime placeholder is assumed to correspond to a unique prime number that does not appear in the prime factorization of any literal integer terms that appear in the numerator or denominator of any fraction in the program or in the prime factorization of any literal integer terms in the initial program state integer. Effectively, prime placeholders provide a way to directly address the simulated registers and assign them names, rather than having to document which integers have been arbitrarily assigned to which semantic functions of the program.

For documenting the functionality of the examples, they also make use of comments, which begin with a hash mark (#) and run until the end of the line.

Symmetry vs. Reversibility

Traditionally, in reversible programming languages in which bidirectional code execution is possible, backwards execution of code is assumed to be the same as executing the inverse of the code. However, in REFRACTRAN, this is not generally the case, and the behavior of a fraction list under forward and reverse searches will not, in general, be clearly related in any way. Consider the following fraction sequence:

@temp_1 / @temp_2,
@temp_1 / @flag_1,
@temp_1 / @flag_2,
@temp_1 / @temp_2,

This is a fairly common structure for a fraction sequence, where @temp_1 and @temp_2 are assumed to initially have a power of 0. When a forward search passes through this sequence, it will result in swapping the powers of @flag_1 and @flag_2.

However, when a reverse search passes through this sequence under the exact same circumstances, it will do nothing. Since @temp_1 is assumed to have a power of 0 by default, the program state integer will not be divisible by a fraction with a numerator containing @temp_1, so none of this code can trigger.

Since reverse execution does not undo the effects of forward execution, it is reasonable to ask if this language is even still reversible. The language is still reversible despite lacking this expected symmetry, because every program state still has a single uniquely-identifiable predecessor state. Consider the following program fragment:

...
@numerator1 / @denominator1,
@numerator2 / @denominator2,
...

If we are forward-searching the second fraction, there are two possible ways that we could have reached it. The first option is if we forward-searched the first fraction and failed to match it; the second option is if we reverse-searched the first fraction and successfully matched it, which would have turned the search around and advanced to the second fraction. We can always distinguish between these two possibilities by checking if the program state integer contains all of the factors from the first fraction's denominator.

• If it does not contain all of the factors from the first fraction's denominator, then we must have reached the second fraction by forward-searching the first fraction and failing to match it. If we had instead reverse-searched the first fraction and successfully matched it, then the program state integer would have to contain all of the factors from the denominator.
• If it does contain all the factors from the first fraction's denominator, then we must have reached the second fraction by reverse-searching the first fraction and successfully matched it to turn around. If we had instead forward-searched the first fraction, we would have successfully matched (due to having the factors from its denominator in the program state integer), and would have turned around before reaching the second fraction.

Equivalent logic can be applied during reverse searches (by considering the "next" fraction's numerator instead of the previous fraction's denominator). This process can be applied repeatedly to step backwards through the entire execution history of the program.

As a result of this lack of symmetry, if you want to "rewind" the program state, it is not sufficient to just reverse the search direction; you must reverse the search direction, move to the next fraction in the new search direction, and also reciprocate every fraction in the program. If you then proceed to run the normal evaluation rules, this will always result in the program rewinding to its initial state then halting.

Although fraction lists do not inherently have this symmetry, it is still possible to construct fraction sequences which, under a certain set of assumptions about initial conditions, the forward and reverse behaviors of the fraction sequence are inverses. Any such symmetric fraction sequences have the property that their behavior does not change if you take the reciprocal of every fraction in the sequence. This property, along with the steps required to rewind a program, result from some general properties of REFRACTRAN fraction lists, in which some basic operations on the fraction lists correspond to semantic operations on the behavior of the programs that those fraction lists represent.

Semantic Operations on Fraction Lists

Certain basic operations on the fraction lists correspond to specific operations on the programs represented by those fraction lists:

• Reversing the order of the list is equivalent to replacing the forward and reverse behaviors of the program each with their own inverses. This represents the intuitive idea of "inverting the program".
• Reciprocating each fraction in the list is equivalent to replacing the forward and reverse behaviors of the program each with one another's inverses.
• Both reversing the order of the list and reciprocating each fraction in the list is equivalent to swapping the forward and reverse behaviors of the program.

REFRACTRAN appears to behave as an inverse monoid under concatenation of fraction lists over the equivalence classes of fraction lists that compute the same function. Reversing the fraction list becomes the "inversion" operation of the inverse monoid.

Additionally, assuming that no cancellation occurs, multiplying all of the fractions in a fraction list by a shared constant fraction is equivalent to making the entire program conditional on the factors in the constant. Forward searches become conditional on the factors in the denominator, and reverse searches become conditional on the factors in the numerator. Conveniently, when a fraction within this conditional sequence is matched, it will automatically populate the needed condition for the opposite direction search, so it is a very clean way of introducing conditionals. This can be utilized in creating control flow operations.

Computational Class

REFRACTRAN is Turing complete, as it is capable of a very direct simulation of Retrograde.

Retrograde Simulation

We can represent Retrograde's memory state using 4 prime powers as registers:

• One register, @left_tape, is an encoding of the tape trailing off to the left.
• One register, @right_tape, is an encoding of the tape trailing off to the right.
• One register, @current_is_1, has a power of 1 if the current Retrograde bit is 1, and 0 otherwise.
• One register, @current_is_0, has a power of 1 if the current Retrograde bit is 0, and 1 otherwise.

The two tape registers represent each direction of the tape as a "stack" of bits, with the least significant bit of the number being the top of the stack. Bits are pushed into the stack by doubling it and then adding the new bit, and bits are popped from the stack by dividing the stack by 2 and extracting the remainder.

In addition, the implementation makes use of a number of temporary registers. Two temporary registers, @temp_1 and @temp_2 are assumed to initially have a power of 0 and are used across all of the instruction implementations. Each simulated turn statement also gets its own set of four additional temporary registers that are specific to its level of nesting; the functions of these additional temporary registers will be explained in the section on turn statements.

Our initial integer value for the program will always just be @current_is_0. This represents a memory state where the current bit is 0, the tape to the left and right are filled with zeroes, and all temporary registers have a power of 0.

With this memory setup, we can then map each Retrograde instruction to a fraction list that implements an exactly equivalent behavior. To implement a Turing complete subset of Retrograde, we only need to implement toggle (*), right shift (>), and turn statements ({}).

Toggle

With the memory model specified above, a toggle would have the function of swapping the powers of @current_is_1 and @current_is_0. In order to implement this toggle instruction, we can take advantage of the fact that toggle can be implemented as a sequence of a forward half-toggle and a reverse half-toggle, and first build implementations of those two instructions, which are much simpler to reason about

Forward Half-Toggle

A forward half-toggle is the same structure discussed above in the Symmetry vs. Reversibility section:

@temp_2 / @temp_1,
@temp_2 / @current_is_0,
@temp_2 / @current_is_1,
@temp_2 / @temp_1,

• If @current_is_1 matches, then it will populate @temp_2, take one step in reverse, immediately match the previous fraction, and populate @current_is_0.
• If @current_is_0 matches, then it will populate @temp_2, take one step in reverse, immediately match the previous fraction, and populate @temp_1. It will then progress to the fourth fraction, match, populate @temp_2, take one step in reverse, immediately match the previous fraction, and populate @current_is_1

Reverse Half-Toggle

By taking advantage of the property that reciprocating a fraction list replaces its forward and reverse behaviors with one another's inverses, we can construct a reverse half-toggle by simply reciprocating every fraction in the forward half-toggle:

@temp_1 / @temp_2,
@current_is_0 / @temp_2,
@current_is_1 / @temp_2,
@temp_1 / @temp_2,

Combined Toggle

If we execute a forward half-toggle followed by a reverse half-toggle, the result is equivalent to a normal toggle, so our normal toggle can be implemented as:

@temp_2 / @temp_1,
@temp_2 / @current_is_0,
@temp_2 / @current_is_1,
@temp_2 / @temp_1,
@temp_1 / @temp_2,
@current_is_0 / @temp_2,
@current_is_1 / @temp_2,
@temp_1 / @temp_2,

Right Shift

The right shift instruction has a number of moving parts, and it will be easier to explain how it works by first examining the functions served by each of its individual pieces:

Move Power From One Prime to Another

Given a temporary register @temp_1 and a destination register, @to, both with an initial power of 0, the following fraction sequence will move the power of @from to @to, leaving @from with a power of 0:

@temp_1 / @to,
@temp_1 / @from,

Move and Double

Given a temporary register @temp_1 with an initial power of 0 and a destination register, @to, the following fraction sequence will add double the power of @from into @to, then set the power of @from to 0.

@temp_1 / @to * @to,
@temp_1 / @from,

Importantly, @to is not required to initially have a power of exactly 0 for this sequence to work. It can have a power of either 0 or 1, and this turns out to be essential to incorporating the value of the current bit into the stacks representing each direction of the tape.

Move and Halve, With Remainder

Given a temporary register @temp_1 and a destination register, @to, both with an initial power of 0, the following fraction sequence will divide the power of @from by 2, placing the quotient in @to and leaving the remainder in @from.

@temp_1 / @to,
@temp_1 / @from * @from,

Forward Right Shift

Using all of these building blocks, we can construct a fraction sequence that performs the equivalent of a right shift during forward searches:

# Move the power of `@current_is_1` to `@temp_2`
# We set `@current_is_0` if any value is transferred so that the current cell flags are
# in a normalized state to accept the new value of the cell.
@temp_1 / @temp_2 * @current_is_0,
@temp_1 / @current_is_1,

# Move and double contents of `@right_tape` to `@temp_2`.
@temp_1 / @temp_2 * @temp_2,
@temp_1 / @right_tape,

# Move `@temp_2` back to `@right_tape`
# The combination of these last three steps have effectively pushed the current
# cell value into the `@right_tape` stack.
@temp_1 / @right_tape,
@temp_1 / @temp_2,

# Now we do the inverse.
# Move `@left_tape` to `@temp_2`
@temp_1 / @temp_2,
@temp_1 / @left_tape,

# Move and halve contents of `@temp_2` to `@left_tape`, leaving a remainder in `@temp_2`
@temp_1 / @left_tape,
@temp_1 / @temp_2 * @temp_2,

# Move the power of `@temp_2` to `@current_is_1`
# We clear `@current_is_0` if any value is transferred so that only one of the two
# current flags is set.
@temp_1 / @current_is_1,
@temp_1 / @temp_2 * @current_is_0,

Since every fraction contains a temporary register in its numerator, this fraction sequence will do nothing during reverse searches.

Reverse Left Shift

If we want to create a fraction sequence that performs a left shift during reverse searches, we can take advantage of the rules discussed in an earlier section, and simply reciprocate all of the fractions in the forward right shift:

@temp_2 * @current_is_0 / @temp_1,
@current_is_1 / @temp_1,
@temp_2 * @temp_2 / @temp_1,
@right_tape / @temp_1,
@right_tape / @temp_1,
@temp_2 / @temp_1,
@temp_2 / @temp_1,
@left_tape / @temp_1,
@left_tape / @temp_1,
@temp_2 * @temp_2 / @temp_1,
@current_is_1 / @temp_1,
@temp_2 * @current_is_0 / @temp_1,

Since this replaces the behavior of each direction with the other's inverse behavior, the forward behavior becomes nothing, and the reverse behavior becomes a left shift.

Combined Right Shift

By concatenating these two independent shifts together, we can construct a complete right shift, which shifts right during forward searches and shifts left during reverse searches:

@temp_1 / @temp_2 * @current_is_0,
@temp_1 / @current_is_1,
@temp_1 / @temp_2 * @temp_2,
@temp_1 / @right_tape,
@temp_1 / @right_tape,
@temp_1 / @temp_2,
@temp_1 / @temp_2,
@temp_1 / @left_tape,
@temp_1 / @left_tape,
@temp_1 / @temp_2 * @temp_2,
@temp_1 / @current_is_1,
@temp_1 / @temp_2 * @current_is_0,
@temp_2 * @current_is_0 / @temp_1,
@current_is_1 / @temp_1,
@temp_2 * @temp_2 / @temp_1,
@right_tape / @temp_1,
@right_tape / @temp_1,
@temp_2 / @temp_1,
@temp_2 / @temp_1,
@left_tape / @temp_1,
@left_tape / @temp_1,
@temp_2 * @temp_2 / @temp_1,
@current_is_1 / @temp_1,
@temp_2 * @current_is_0 / @temp_1,

Turn Statement

For the implementation of turn statements, each level of nesting of turn statements is assigned its own set of 4 temporary registers:

• @jump_from_outside_N
• @jump_from_inside_N
• @inner_reverse_N
• @inner_forward_N

Each N should be replaced with the index of the level of nesting. All of these registers will initially have a power of 0 when the program starts, and will be returned to 0 when the turn statement exits.

Additionally, recall from an earlier section that multiplying each member of a fraction sequence by a common fraction makes that fraction sequence conditional on the denominator of the common fraction when searching forward, and conditional on the numerator of the common fraction when search in reverse. This fact is exploited to make the execution of the instructions within the turn statement conditional on @inner_reverse_N / @inner_forward_N.

The implementation of the turn statement is given here. It is annotated with comments explaining the function of each smaller block of fractions. Fraction blocks that are executed during a forward search are annotated with [Forward] and those that execute during a reverse search are annotated with [Reverse].

# [Forward] Begin "jump from outside" if current cell is 1.
@temp_1 / @jump_from_outside_N,
@temp_1 / @current_is_1,

# [Reverse] Terminate "jump from outside". Reset the `@current_is_1` flag, which
# is cleared during jumps, and turn on the `@inner_forward_N` flag, so that the
# block will be executed.
@jump_from_outside_N / @current_is_1 * @inner_forward_N,

# [Reverse] Terminate "jump from inside". Reset the `@current_is_1` flag, which
# is cleared during jumps.
@jump_from_inside_N / @temp_1,
@current_is_1 / @temp_1,

# [Reverse] Begin "jump from inside" and turn off `@inner_reverse_N` if current
# cell is 1.
@current_is_1 * @inner_reverse_N / @jump_from_inside_N,

# [Forward] Turn on `@inner_forward_N` flag if current cell is 0.
@temp_1 / @temp_2,
@temp_1 / @current_is_0,
@temp_1 / @current_is_0 * @inner_forward_N,
@temp_1 / @temp_2,

# [Reverse] Turn off `@inner_reverse_N` flag if current cell is 0.
@temp_2 / @temp_1,
@current_is_0 / @temp_1,
@current_is_0 * @inner_reverse_N / @temp_1,
@temp_2 / @temp_1,

# [INSERT CONTENT OF BLOCK HERE, multiply all by `@inner_reverse_N / @inner_forward_N`]

# [Forward] Turn off `@inner_forward_N` flag if current cell is 0.
@temp_1 / @temp_2,
@temp_1 / @current_is_0 * @inner_forward_N,
@temp_1 / @current_is_0,
@temp_1 / @temp_2,

# [Reverse] Turn on `@inner_reverse_N` flag if current cell is 0.
@temp_2 / @temp_1,
@current_is_0 * @inner_reverse_N / @temp_1,
@current_is_0 / @temp_1,
@temp_2 / @temp_1,

# [Forward] Begin "jump from inside" and turn off `@inner_forward_N` if current
# cell is 1.
@jump_from_inside_N / @current_is_1 * @inner_forward_N,

# [Forward] Terminate "jump from inside". Reset the `@current_is_1` flag, which
# is cleared during jumps.
@temp_1 / @current_is_1,
@temp_1 / @jump_from_inside_N,

# [Forward] Terminate "jump from outside". Reset the `@current_is_1` flag, which
# is cleared during jumps, and turn on the `@inner_reverse_N` flag, so that the
# block will be executed.
@current_is_1 * @inner_reverse_N / @jump_from_outside_N,

# [Reverse] Begin "jump from outside" if current cell is 1.
@current_is_1 / @temp_1,
@jump_from_outside_N / @temp_1,

There are 8 overlapping cases in this implementation (entering vs exiting, current is 0 vs current is 1, forward vs reverse), but the general structure is that there are two paths into and two paths out of the block in each direction. If the current bit is 1 then the condition flags that allow the body of the turn statement to be executed are left with a power of 0 while the search moves to the opposite side of the body and turns around. However, if the current bit is 0, then simpler blocks of fractions just turn those condition flags on as the search enters or off as the search exits.