FRACTRAN is a beautiful and beautifully frustrating language. It was devised by John Conway, better known for his Game of Life, which, like FRACTRAN, is built on a simple premise leading to not-so-simple results. Mark Chu-Carroll of Good Math Bad Math described FRACTRAN as “absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation.” First published in the Proceedings of the 1972 Number Theory, it was popularized in his 1998 Book of Numbers (co-written with Richard Guy).
That bizarrely elegant concept is Gödel numbering, where mathematical functions are mapped to numbers and single numbers represent multiple values, devised by Gödel for his Incompleteness Theorem. We will be using it for much more modest aims here.
Returning for a moment to our grade school math, any number that can't be divided by any other number—apart from itself and one—is prime. They are the numbers 2, 3, 5, 7, 11, 13, 17, and so on. Since primes can't be divided, we can think of them as the DNA of other numbers. Take the number 6. We can represent it as 2 x 3, its prime factorization. The number 12 is factorized to 2 × 2 × 3, or 2² × 3. 1008's prime factorization is 2⁴ × 3² × 7.
In FRACTRAN, each primary number is a variable. Their exponents are the values for those variables. The current state of the FRACTRAN program is held all as a single number, whose prime factorization holds these variables. For example, if the current state is 1008 (again, factorizing to 2⁴ × 3² × 7), var_2 has the value 4, var_3 has the value 2, var_7 has the value 1, and all other variables are unassigned.
Since there are infinite primes, we have as many variables as we need, but held in a single number.
A FRACTRAN ADDER
Let's look at an actual FRACTRAN program to see how this works. In many introductions—including many of Conway's lectures—the example given is his PRIME GAME, which produces the primes. While this is a beautiful use of FRACTRAN, I find it can confuse people trying to get grounded in the FRACTRAN language, since we're now using primes as both our variables and the output of the program—the very thing we're trying to calculate.
Instead, let's try the simplest example: a program that adds two numbers together. This fraction is the adding program:
3 / 2
How we will execute it as a FRACTRAN program: we will take a number, the input to our program. If multiplying it by this fraction will give us an integer, we will do so. Otherwise, we will stop and consider the program complete. We will do this repeatedly until we can no longer produce an integer with this method.
Why this will work: The number we're using as input will have 2 and 3 as factors and therefore variables (var_2 and var_3), and their exponents are their starting values. By multiplying and dividing by its factors, we are changing these primes' exponents.
For example, let's add 4 and 2. We can use the prime numbers 2 and 3 to hold them. This is 2⁴ × 3², or:
var_2 = 4
var_3 = 2
2⁴ × 3² is 144, our starting state.
First go, multiplying our value with the program:
144 × 3 / 2 = 216, which factors to 2³ × 3³
We have subtracted one from var_2, and added it to var_3. Since 216 can divide evenly by 2 (our denominator), we do this again:
216 × 3 / 2 = 324 or 2² × 3⁴. And so on:
324 × 3 / 2 = 486 or 2¹ × 3⁵
486 × 3 / 2 = 729 or 3⁶
Since our working value (729) is now odd, we have exhausted the program; it can no longer be divided by 2 and result in an integer.
The important thing to note is that the 3 / 2 fraction is arbitrary. We could have created a fraction with any two primes: 5 / 3, or 7 / 11, and used those primes to create the input to our program. 2 and 3 are used by convention, as the lowest primes. But any single fraction of two prime numbers is an adder, by virtue of how exponents relate to multiplication and division—and so to the numerator and denominator of the program. Furthermore, if we fed the program an odd number instead of 144 to begin, no addition would happen.
It may seem like this is a hard way to add two numbers, but we’ll next see how more complex algorithms are enacted in FRACTRAN. To continue, we’ll need the complete set of rules:
- A FRACTRAN program is a set of fractions
- The input to the program is a single composite number, which is also the current state of our program
- We consider each fraction in order, in terms of our current value
- If multiplying it with that fraction will give us an integer, we multiply it and start again at the beginning of the list
- We stop when there are no more fractions that will give us an integer result (make it to the end of the list)
A FRACTRAN MULTIPLIER
One multiplication program looks like this (source: Good Math, Bad Math) :
385 / 13, 13 / 21, 1 / 7, 3 / 11, 7 / 2, 1 / 3
Let's break it up into prime numbers to see what we're dealing with:
(7 × 11 × 5) / 13
13 / (3 × 7)
1 / 7
3 / 11
7 / 2
1 / 3
So, we have six variables, the primes 2, 3, 5, 7, 11, and 13. This program takes two inputs, primes 2 and 3, and places the product in prime 5. For simplicity, let's multiply low numbers. We won't use 2 and 2, in the case that we've created another adder by mistake. Let's go with 2 and 4. That means starting with 2² × 3⁴, which is 324. If we succeed, the result will be 5⁸, or 390625.
Let's consider what will happen when we run our input through this series of fractions. In the first fraction, if the number is cleanly divisible by 13, the variables 7, 11, and 5 will all be incremented. Think of this as the reverse of what we did in the adder, but for three variables at once. For the second fraction, both the variables var_3 and var_7 would need to be matched.
Here's how the first run of the program looks:
324 × 385 / 13 = NOT AN INTEGER (AS NOT DIVISIBLE BY 13), SKIPPING....
324 × 13 / 21 = NOT INT...
324 × 1 / 7 = NOT INT...
324 × 3 / 11 = NOT INT...
324 × 7 / 2 = 1134
With this match, we go back to the first fraction. In the second round, we find a match much faster:
1134 × 385 / 13 = NOT INT...
1134 × 13 / 21 = 702
In the third round, we know we will match the first fraction since we had just multiplied our value by 13, its denominator:
702 × 385 / 13 = 20790
The next round, we hit the second fraction again:
20790 x 385 / 13 = NOT INT...
2079 x 13 / 21 = 12870
We know that this second fraction means the first fraction will then fire again.
It should be apparent by now that the basic structure of this program is a series of larger and larger conditional loops.Or, more precisely, for a program with the fractions n1 / d1, (n2_1 * n2_2) / (d2_1 * d2_2), we would have this:
while(true) {
if (d1) { d1--; n1++; continue;}
if (d2_1 && d2_2) { d2_1--; d2_2--; n2_1++; n2_2++; continue;}
break;
}
In our program here, the first fraction looks like this:
if (var_13) { var_13--; var_7++; var_11++; var_5++; continue;}
The objective of our program is to multiply var_2 by var_3, so we know we want to loop once for enumeration of var_2 and of var_3. The last two fractions have 2 and 3 as their denominators, which essentially creates those two nested loops.
While it can be useful to generate a complete program like above to actually walk through the code, this structure doesn't add much clarity to the actual functioning of the code (it doesn't help us visualize those loops). We can also try to represent the fractions as transitions, keeping in the looping structure and the fact that the left side is always decremented, even when there is nothing on the right:
Fraction 1: v13 --> v7, v11, v5
Fraction 2: v3, v7 --> v13
Fraction 3: v7 -->
Fraction 4: v11 --> v3
Fraction 5: v2 --> v7
Fraction 6: v3 -->
We know Fractions 5 and 6 are these nested loops, but the tricky part is how to get the adder inside. If we had a program like this:
5 / 1, 1 / 2, 1 / 3
We would successfully add to v5, but we would do this forever; there is no way to get past that first fraction since 5 / 1 will match every state of the program! Instead, we need to use flags to make sure that the incrementing happens successfully. As we'll see, the main reason for having more than one flag is that if we test a flag, we also decrement it, which usually means turning it off.
Of these, v7 is the most obvious. It's set in the looping of v2, and indicates we're ready to add the value of v3 to v5, our output. It's set in the first fraction we actually hit.
Once v7 is live, we next trigger Fraction 2. Fraction 2 is just there to fire Fraction 1. They will go back and forth until v3 is depleted, decrementing each time we hit Fraction 2. At that point, we hit Fraction 4, which replenishes v3 from v11, which is the temporary variable holding v3's value. This works because we're hitting Fraction 4 repeatedly (we've depleted v13 and v7 by then). v11 gets v3 back to its original state for the next loop.
Next, we hit Fraction 5, which counts v2 down by one, and starts the loop again.
Fraction 6 is a clean-up fraction, which drains v3 of any remaining value, meaning that at the end of the program, we have both v2 and v3 set to zero.
Hopefully it is now apparent why we need the v7 flag (indicating a current add operation) and v11 as temp store of v3 value. But v13 looks less useful. Since Fractions 1 and 2 always fire together, why not combine them and get rid of v13, like so?:
v3, v7 --> v7, v11, v5
This would put v7 on both sides of the fraction, so it would reduce and cancel the 7 out entirely! We need to keep the v7 flag alive through the entire adding of v3 to v5; this is the cost of decrementing every time we test a variable. So that fraction is split into two, with v13 as the flag from one to the other. The one that fires first is second (Fraction 2).
I hope this gives a taste of the utter insanity of writing code in this language.
With branching, looping, incrementing and decrementing, we can see at least see how FRACTRAN is Turing Complete. It gives us as much as brainfuck does. However, with the concentric looping structure of FRACTRAN programs—where every time we match a denominator, we get sent back to the start—state is very hard to visualize and manage.
GOING FURTHER
The best intro to FRACTRAN is perhaps by John Conway himself in this video, which starts with the related Collatz problem and works into the PRIME GAME, the original FRACTRAN prime generator. It moves slowly at first but gets rather advanced. Watching him write out the prime generator's fractions from memory is quite exciting, though.
If you can find a copy, the book Open Problems in Communication and Computation explains state in FRACTRAN very clearly. Wikipedia presents another version of multiplication in FRACTRAN, with a chart showing state, which may or may not make things more clear (I don't find it particularly helpful, but others have).
For more visceral proof that FRACTRAN is actually Turing Complete, check out the FRACTRAN interpreter written in FRACTRAN. Written in only 48 fractions, I believe is still the shortest of its kind. It includes a nice explanation of how to generate code for FRACTRAN.
UPDATED 4/12/2020: On the sad news of John Conway's death, and increased attention to this page, the post has been expanded and hopefully clarified a bit.
UPDATED 12/12/2020: Fixed the math, thanks to @hundredrabbits, who wrote a nice command-line FRACTRAN interpreter in C, you can find it here.