In honor of Conway, there have been a few FRACTRAN-related questions and answers on https://codegolf.stackexchange.com/ https://codegolf.stackexchange.com/ htt

In honor of Conway, there have been a few FRACTRAN-related questions and answers on https://codegolf.stackexchange.com/ https://codegolf.stackexchange.com/ https://codegolf.stackexchange.com/a/203685 https://codegolf.stackexchange.com/a/203685 An eight-fraction program that counts the number of iterations until the Collatz sequence reaches 1. https://codegolf.stackexchange.com/a/203682 https://codegolf.stackexchange.com/a/203682 A seven-fraction program that determines whether the Collatz sequence reaches 1. https://codegolf.stackexchange.com/a/203856 https://codegolf.stackexchange.com/a/203856 Solves some arbitrary codegolf problem. I remember coming across FRACTRAN long long ago on some esolang site and wondering how anyone could write anything in it to solve even the simplest of problems. What unlocked it form me was realizing that FRACTRAN programs can be thought of as a list of chemical reactions that are tried sequentially, where if any succeed we start back at the first reaction. Since fractions are reduced, there is an arbitrary constraint that the reactions have no catalysts, which are chemical species that are both reagents and products in the same reaction. Also, unlike real chemistry, reactions don't have to conserve mass/energy. (If you like, a FRACTRAN program is a list of rewrite rules in a commutative monoid, where a rule only applies if none of the previous can apply.) With this in mind, you can write a program that takes two numbers, represented as the numbers of A and B species, and returns the sum as the number of C species like so: A -> C B -> C Or, how about multiplication instead? We need some intermediate products U1, U2, and X to calculate this: U1 + B -> U2 + C + X U2 -> U1 U1 -> 0 X -> B A -> U1 This does, roughly, "for each A, take each B and add it to C." Since adding something to something is destructive, it uses the X species to save the old value of B. The presence of U1 or U2 indicates the program is in this addition loop. There is something wonderfully simple about FRACTRAN as a model for computation. Even Turing machines seem complicated in comparison. By the way, Conway in his "FRACTRAN: a simple universal programming language for arithmetic" describes how to construct larger programs with control flow. From the above point of view, you essentially add a new species like LINE100 to the left-hand side of each reaction and a corresponding LINE101 to the right-hand side. In this case, the program would go from "line 100" to "line 101." --- While there is an obvious way to write an interpreter for FRACTRAN, on anything but the simplest of programs it will run absurdly slowly due to the fact that everything is done with unary arithmetic (in the exponents of the primes). Is your input an ASCII-encoded string and you want to get the first character? You're going to need a loop that repeatedly subtracts 256 from the input to do modular reduction. Good luck parsing anything substantial before the universe dies! Someone figured out how to accelerate these sorts of loops. It seems like it looks for constructs that add or subtract constants to the state variables, and then it skips over the intermediate steps and calculates their total effect. https://pimlu.github.io/fractran/ https://pimlu.github.io/fractran/ (It looks like it was a term project, and they have a paper about it in the GitHub repository.)