Remembering John Conway's FRACTRAN | Hacker News Reader

Remembering John Conway's FRACTRAN

raganwald.com

84 pointsbraythwayt14 comments

> Manually simulating ideal computing machines loses its lustre once you’ve manually verified that 3 * 13 = 39

"Our love for each other was stronger than ever, but I preminisced no return of the salad days." - H.I. McDunnough in Raising Arizona (or Reginald Braithwaite and ideal computing machines, apparently)

Anyway, from a high-level view this is a lovely tribute to John Conway, who deserves to be remembered for more than just the Game of Life. From a less high-level view, I'm halfway through article, and it is excellently written but so dense in content that I need to take a break and digest it in multiple readings! But thank you for writing about this subject in such an accessible manner.

I like the idea, but needing a conversion function that isn’t written in the language (on both input _and_ output), IMO, is a bit of a blemish.

If, to add a and b, one first has to compute 2^a 3^b, and afterwards, compute ³logx, how is that better than just using a+b as input, running the empty program, and looking at its output?

Shouldn't both the conversion functions technically be implementable in Fractran as well though? Perhaps these were left as exercises for the reader ;)

This is the repo where I wrote my various implementations and experiments:

https://github.com/raganwald/FRACTRAN/

One of the versions that didn't make it into the essay used this pipelining notation for combining a FRACTRAN program with the starting seed:

  10 |> 3/11 847/45 143/6 7/3 10/91 3/7 36/325 1/2 36/5

I had some idea that this could evolve into writing different fractran programs to handle converting a seed in ordinary integer form into whatever the core function wanted, filtering the values of n as we do with PRIMEGAME, or picking the last value of n as we do with FIBGAME.

Doubt anything will come of it, but anyhow, the original idea seems close to what you're suggesting. What would make the pipelining ida interesting, of course, would be compiling such notation to a single FRACTRAN program.

What is it you think we're doing when we write `2+2`, if not encoding an expression using something called "ASCII?" FRACTRAN simply asks us to use a different encoding, "Prime Factorization."

:-D

That being said, you ask a really, REALLY interesting question. Why not write the conversion from ASCII (or anything else) to FRACTRAN as well as whatever function we're trying to compute?

The answer, I suggest, lies in what we're using FRACTRAN for. Conversion to and from ASCII is what we might call "incidental complexity," it's useful to humans, but not at the core of whatever function (e.g. Fibonacci, digits of PI, prime numbers, universal FRACTRAN interpretation) we're studying.

Were we to bake ASCII encoding in, the resulting FRACTRAN program would be 95% ASCII manipulation and only 5% fibonacci (or whatever).

This highlights, of course, why non-esoteric languages have tools for modularization and abstraction. When we write "Hello, World," we rely on standard libraries and other tools that do the things our program isn't about.

HN has discussed FRACTRAN before, of course: https://hn.algolia.com/?q=fractran

If this post has anything new to contribute, it will be the discussion around Minsky Machines, a sketch of Conway's own interest in using POLYGAME to derive a proof about the undecidability of arbitrary Collatz problems, and as usual with my posts, a series of JavaScript implementations.

Surprisingly little—not many comments but they're pretty good and https://malisper.me/building-fizzbuzz-fractran-bottom/ was a good article.

2017: https://news.ycombinator.com/item?id=14202367

2016: https://news.ycombinator.com/item?id=11894141

2011: https://news.ycombinator.com/item?id=3119937

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

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 A seven-fraction program that determines whether the Collatz sequence reaches 1.

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/ (It looks like it was a term project, and they have a paper about it in the GitHub repository.)

There are a few people who've written up their approaches for writing what amounts to pseudocode-to-FRACTRAN compilers.

The Collatz-generating program given in TheFrumiousArticle was generated by writing a Magnificent Minsky Machine first, and then using the example Minsky->FRACTRAN compiler.

Thank you for reminding me about the code golf examples, I saw them early in my writing research, and meant to include a note about them.

I'll do that now!

I'd call the reaction notation pseudocode inasmuch as I'd call assembly language pseudocode or prime factorizations pseudocode -- they're equivalent in completely mechanical way. (Caveat: there needs to be a prime<->species assignment block, too.)

A way I'd been experimenting with FRACTRAN is with a slightly different notation, Python:

   B = 2
   A = 3
   M2 = 5
   Div = 7
   M1 = 11
   Count = 13

   prog = [
       (M1 * A, M2 * B**10),
       (M1, M2 * A),
       (M2 * A * Div, M1 * B),
       (M2 * B**4 * Div, M1 * A),
       (M2, Count),
       (B, A),
       (A**2, Div),
       (Div, M1)
   ]

It uses multiplicative rather than additive notation. All that's left is to take the RHS and divide it by the LHS.

---

On HN a while back, someone posted something about how Petri nets are the same as rewrite rules in a commutative monoid, and seeing as FRACTRAN is sort of a system of rewrite rules, I thought to see whether anyone had made the connection before, and sure enough there's a paper. Cook, Soloveichik, Winfree, and Bruck, "Programmability of chemical reaction networks." http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.155...

You're right!

I propose that there is an informal difference between pseudocode, and a specification for a machine: Typically, pseudocode doesn't have a mechanical compiler.

It may not have a mechanical compiler for some technical reason (such as inconsistent syntax or impossible semantics), or it might just be too much bother to write a real compiler and sort out how to make all possible program work.

But yes, going by this, the moment one writes a pseudocode-to-FRACTRAN compiler, it ceases to be pseudocode and becomes a domain-specific language for writing FRACTRAN programs.

+1!

I agree, but I'm saying something stronger here. The reaction notation is equivalent to a FRACTRAN program. Given a prime<->species correspondence, it survives a round trip to and from fractional notation, so to speak ("assembly" and "disassembly"). It's just another way of writing prime decompositions.

Perfectly logical agents who can see the entirety of logical consequence would think "eh, what's the big deal? it's equivalent!" But, for whatever reason, the notation finally made me "get" FRACTRAN.

Oh yes, I embrace the distinction you're drawing, I tried to make the same point about "magnificent" Minsky Machines and FRACTRAN programs.

They aren't just "computationally equivalent," they're equivalent "all the way down."

Another one I had some fun with: write a FRACTRAN->brainfuck compiler!

https://codegolf.stackexchange.com/questions/5210/convert-fr...

My solution was nowhere near competitive but I sure had fun with it.

Reply on news.ycombinator.com