A Ridiculous Logical Language

August 9, 2015 3:20 AM

Fractran (previously) is a Turing Complete language invented by John Conway (yes that John Conway) that uses only a simple list of fractions to form each program. Astonishingly it takes only a list of 14 fractions to form a program to generate all the primes. Here's the man himself explaining how it all works.

If you'd like to play around a little with Fractran, implementations in many languages can be found here. Or for the truly adventurous there even exists a Fractran self-interpreter.

posted by Proofs and Refutations (38 comments total)

O_o
posted by sidereal at 4:19 AM on August 9, 2015

teh smartz iz strong with this one ...
posted by oheso at 4:30 AM on August 9, 2015

There's an odd part of me which is really satisfied when people who made promising things in the more abstract realms (maths, psychology, boopers) before make completely different but equally promising things. There's actually smart people out there.

This is cool. I wonder if any significant problems could use it for computation, given the prime program.
posted by solarion at 4:36 AM on August 9, 2015 [3 favorites]

in case people aren't understanding what's happening here, this is largely based a round a "trick" that lets you store multiple numbers inside a single number. it's called godel numbering and is based on the use of prime numbers.

prime numbers are numbers that are not divisible by other numbers (just 1 and themselves), so 5 is a prime number, but 4 (=2x2) and 6 (=2x3) are not. by decree, 1 itself is not a prime.

the trick is pretty simple - you can make a single (but often very large) number by using the prime numbers as "counters".

for example, if you want to store a bunch of natural numbers (1, 2, ....) with duplicates, you first make a list of the primes: 2, 3, 5, 7, 11, 13, 17...

then you take the numbers you want to encode. let's say we want to encode 1,3,3. for each value, we use the "nth" prime number. so 1 becomes 2 (the first prime) and 3 becomes 5 (the third prime). then we multiple those together the appropriate number of times (we have two 3s so we multiple 5 twice): 2x5x5 = 50.

then 50 "encodes" 1,3,3. you can extract the "hidden" values by factoring the number: 50 = 2x5x5 and then working backwards from the position of the primes in the list: 2 -> 1, 5 -> 3, 5 -> 3.

once you get that, you might see that this is really "just" a way of writing a "program" that changes what numbers are hidden inside the big number made from primes. a lot of using this to write useful programs comes from working out how to squeeze meaning from a simple list of numbers, rather than from the language itself.
posted by andrewcooke at 4:58 AM on August 9, 2015 [54 favorites]

But what when you run out of primes.
posted by Joe in Australia at 5:52 AM on August 9, 2015 [12 favorites]

does encoding numbers in numbers (so you use 2^50 instead of 50) gets you beyond aleph-0? i suspect not, but i can't see how to order them nicely.
posted by andrewcooke at 6:26 AM on August 9, 2015

Ooh, Fractran! Six years ago, I spent the summer reading about variants of the Collatz conjecture, because I needed it for my own research. Fractran is one of those variants. If you are interested in the history of Fractran, three articles come to mind.

Conway's first article, titled "Unpredictable iterations", appeared in the proceedings of the 1972 Number Theory Conference. There, Conway introduced a precursor of Fractran, vector games, as a generalization of the Collatz function.

Towards the end of the article, he remarks: "Perhaps some industrious reader will produce a short prime-generating vector game". This prime game was then published in 1983 by Richard K. Guy in this article (which I think you can read for free after registering -- it is quite easy to read, and even has two cute illustrations).

Conway then introduced Fractran (with a version of that "prime game") in a 1987 article. Sadly, this article is behind a paywall, but if you can access it, it is quite fun to read. The sections have titles like "Your Free Samples of FRACTRAN", "Avoid Brand X", and "Only FRACTRAN Has These Star Qualities" (which list claims like "Makes workdays really easy!" and "Gets those functions really clean!").

Both Conway articles were reprinted with some additional commentary in Jeffrey C. Lagarias' book The Ultimate Challenge: The 3x+1 Problem, which contains much more information on unpredictable iterations.

If you want to read more about Fractran and related topics, Lagarias' book is a great collection of stuff that is quite hard to track down. (Sadly, it came out a year after I had tracked down all that stuff, so it wasn't that useful to me anymore. But it's still a cool book).
posted by erdferkel at 6:31 AM on August 9, 2015 [16 favorites]

a lot of using this to write useful programs comes from working out how to squeeze meaning from a simple list of numbers, rather than from the language itself.

This makes me think any L-system-like production rule –

G = (V, ω, P),
where

V (the alphabet) is a set of symbols containing elements that can be replaced (variables)

ω (start, axiom or initiator) is a string of symbols from V defining the initial state of the system

P is a set of production rules or productions defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings, the predecessor and the successor. For any symbol A in V which does not appear on the left hand side of a production in P, the identity production A → A is assumed; these symbols are called constants or terminals.

The rules of the L-system grammar are applied iteratively starting from the initial state.

– can be used to make a single-tape Turing machine. Fractan's replacement rule seems like an L-system production rule, for example.

In that light, Turing completeness seems cool but not all that significant to me! But I could very well be missing something.
posted by ignignokt at 6:37 AM on August 9, 2015 [5 favorites]

ok, i just realised how stupid my idea above was (numbers in numbers). sorry (obviously you can't get above alpeh-0 using just integers, no matter how complicated you make life)
posted by andrewcooke at 6:40 AM on August 9, 2015 [3 favorites]

prime numbers are numbers that are not divisible by other numbers (just 1 and themselves), so 5 is a prime number, but 4 (=2x2) and 6 (=2x3) are not. by decree, 1 itself is not a prime.

Nominated for the Humansplaining Prize, 2015 MeFi Choice Awards ;-)
posted by the quidnunc kid at 6:47 AM on August 9, 2015 [3 favorites]

(The above comment submitted teasingly, and not contemptuously; and with due respect to my fellow MeFite)
posted by the quidnunc kid at 6:48 AM on August 9, 2015 [2 favorites]

This makes me think any L-system-like production rule [..] can be used to make a single-tape Turing machine.

This is not true. What you cite is a context-free L-system (also called 0L-system), and these are far too weak to simulate Turing machines.
posted by erdferkel at 6:55 AM on August 9, 2015 [3 favorites]

Honestly, it's not the Turing completeness I find so appealing about this little gem, it's the straightforward programs it admits. If you worth through a couple of the simple arithmetic programs at the Wikipedia link I think you'll be pleasantly surprised by how easy they are to follow. Even the prime generator is explained sufficiently in Conway's lecture that it's fairly easy to see what each of the 14 fractions is doing, computationally.

Add in the fact that it allows toying directly with Godel numbers and has a strong connection to the Collatz conjecture and I find it to be, like most things Conway has had a hand in, utterly delightful.
posted by Proofs and Refutations at 7:06 AM on August 9, 2015 [5 favorites]

I figured there was a catch like that! But isn't Fractan also context-free? The only input for the rule is the previous iteration's result and no other state.
posted by ignignokt at 7:09 AM on August 9, 2015

3/16 - 5/32 - 1/5 - 317/273

I had the privilege to attend a talk by Conway at MIT, (was proudly the dumbest in the room:) and rather than dry techno-math it went from oh, to omg through 'what(?) no no no', to whoa that's a big number, in just the first few minutes. And it was all very clear and understandable.
posted by sammyo at 7:28 AM on August 9, 2015 [4 favorites]

fwiw, you can encode 3x+1 (or similar chains) in a classic turing machine with just 5 (iirc) states (this is why busy beaver is only known to 4 states). so it's not that big an "advance" over a simple tape. i think.
posted by andrewcooke at 7:39 AM on August 9, 2015

Higher math n00b question from EE-dropout / programming auto-didact: does Fractran (or the prime-encoding aspect of it) have application in cryptography? Thanks.
posted by Artful Codger at 7:44 AM on August 9, 2015

Big Conway fan here. My encounter with Conway was at University of Washington, where he came to give a poorly-advertised series of three lectures in the Math department (late 1980's - I think I was also the proud dumbest in the room). On the first day, about a dozen of us sat in a fairly large room, dumbfounded, as he gave his introduction to Games and Numbers.

Each of us must have gone back to our friends raving about the talk, because the next day he looked around at the packed room saying "well, there are quite a few of you today. Unfortunately for you, I'm going to pick up right where I left off", and proceeded to both astonish, amaze, and befuddle all of us. He's both got an amazing intellect and curiosity, but is also a great explainer and teacher.

Attending that first lecture reinforced my "follow your curiosity" instinct, which has been its own reward in the decades since. Very much enjoying this discussion -- this still isn't the math I'm strongest in, but I find it fun to follow.
posted by dylanjames at 7:59 AM on August 9, 2015 [12 favorites]

Conway fans will enjoy this mini-biography of him in a recent issue of The Guardian.
posted by Obscure Reference at 8:16 AM on August 9, 2015 [11 favorites]

by decree, 1 itself is not a prime.

Not just "by decree" - it's vital for the concept of prime factorisations (as in the Fundamental Theorem of Arithmetic) that 1 is not prime.
posted by iotic at 8:34 AM on August 9, 2015 [4 favorites]

But isn't Fractan also context-free?

Well, the term "context-free" is normally only used for replacement rules on words, while Fractran operates on numbers. (Furthermore, the context in "context-sensitive" does not refer to previous iteration (or replacement) steps, but to where a rule is applied.) One could argue that Fractran is context-sensitive, because the whole current number has to be taken into account, but I don't think that this point of view is fair, as storing numbers is different from storing words.

What makes Fractran (and Collatz-like iterations) so cool is that the computational model uses no states, no tape, no special storage - just a single number.

does Fractran (or the prime-encoding aspect of it) have application in cryptology?

I would be surprised, as the prime-encoding quickly leads to very large numbers.

I think that models like Fractran, Collatz-like functions, small universal Turing machines (etc) have a practical use: Guiding the search for models of computation or query languages that are far less powerful than Turing complete, but behave nicer. (For example, you can guarantee termination, or you can minimize your queries or programs algorithmically. If you have Turing complete models, these things are known to be impossible.)

If your model is strong enough to simulate a Turing machine, or Fractran, it is probably too powerful. While most proofs are done with Turing machines, sometimes it is necessary (or far easier) to use one of the simpler models.

Of course, this is not an immediate practical use, but could be useful nonetheless.
posted by erdferkel at 8:58 AM on August 9, 2015 [5 favorites]

Great post. I'll be in my bunk glider.
posted by comealongpole at 10:03 AM on August 9, 2015

It wasn't til I read the Guardian piece on Conway that I twigged to the fact that he wrote the Game of Life. Someone wrote a version of that to run on my very first computer (~1977) - the RCA COSMAC VIP, an early single-board computer based on the CDP1802. I spent hours messing with that.

I need to revisit that game. Thanks.
posted by Artful Codger at 10:42 AM on August 9, 2015

I guess part of this is just beyond me, but I do not understand how you get from 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... to 2^2, 2^3, 2^5, 2^7, etc. Can someone explain this outside of an hour long video lecture?
posted by kafziel at 12:13 PM on August 9, 2015

kafziel: Most of the numbers in that sequence should be ignored; they represent intermediate steps in the computation. If you take only those numbers that are actually powers of 2, you get the sequence 2^2, 2^3, 2^5, 2^7, etc. The OEIS has a file with the first 8000 numbers; you'll find 4 = 2^2 as number 20 in the sequence, 8 = 2^3 as number 70, 32 = 2^5 as number 282, and 128 = 2^7 as number 711. But you won't find 16 = 2^4 or 64 = 2^6 anywhere in the sequence, because 4 and 6 are not primes.
posted by Tau Wedel at 12:26 PM on August 9, 2015 [2 favorites]

Ahhh, that makes sense. So it contains a set of identifiable powers of two, but also a lot of junk data in the output. Interesting.

I assume then that this is not an efficient method of generating large primes?
posted by kafziel at 12:31 PM on August 9, 2015

It is horrendously inefficient. To quote the Wikipedia article in the FPP:

Given input of the form 2^n 7^m where 0 ≤ m < n, the algorithm tries to divide n+1 by each number from n down to 1, until it finds the largest number k that is a divisor of n+1.

The algorithm uses trial division, a quite slow method, to identify primes, and it even implements it in a particularly inefficient way by starting from n and moving down instead of starting from 2 and moving up. What makes the program interesting is mainly that it demonstrates that despite the seemingly simple rules of FRACTRAN, you can get mathematically interesting results from a fairly short program.
posted by Tau Wedel at 12:46 PM on August 9, 2015

Thanks for the article links, erdferkel.
posted by benito.strauss at 3:44 PM on August 9, 2015 [1 favorite]

Fractran is one of my favorite toy languages. What few people know is that it has a (tenuous) connection to chemistry. Consider the "prioritized" chemical reaction network model, where an ordered list of "abstract" chemical reactions are given. "Abstract" here means that the named species are hypothetical -- we don't know what they are in the real world, but they act according to the standard rules of chemical reactions: the reactants are consumed and the products are created whenever the reaction takes place. "Prioritized" means that the reactions are listed from "fastest" to "slowest", and the "fastest" reaction that can take place always will take place next. (This part isn't realistic, because with integer counts of molecules in a well-mixed small volume, which reaction takes place next is probabilistic based on reaction rates.)

The connection to Fractran is straightforward. Associate each prime number with a species name, e.g. 2=A, 3=B, 5=C, 7=D, 11=E, 13=F, 17=G, 19=H, 23=I, 29=J, etc. If the chemical system contains 3 A's, 1 C, and 2 E's, that corresponds to the Fractran state 2^3 * 5^1 * 11^2 = 4840. Now, rewrite each fraction in a Fractran program as a chemical reaction where the numerator becomes the products, and the denominator becomes the reactants. E.g. 78/85 becomes C+G -> A+B+F because 5*17=85 and 2*3*13=78. This chemical reaction can occur only if there is at least one C and at least one G, corresponding to a Fractran number that is a multiple of 85. Dividing by 85 corresponds to removing one C and one G from the chemical system; multiplying by 78 corresponds to adding one A, one B, and one F. Thus be behaviors of the prioritized chemical reaction network is in exact correspondence with the execution of the Fractran program.

So, to see the Fractran program for computing primes in a different light, note that it is identical to the following prioritized chemical reaction network starting with a single molecule of species A:

D+F -> G
C+G -> A+B+F
B+G -> H
A+H -> I
B+E -> J
J -> D+E
I -> C+H
H -> D+E
G -> 0
F -> E
E -> F
A+D -> B+C
A -> B+C
0 -> C+E

I wrote 0 where either there are no products, or where there are no reactants (i.e. the reaction can always occur, without consuming anything).

Whenever the chemical system contains exclusively A's, there will be 2^p A molecules, where p is the next prime number.
posted by brambleboy at 6:35 PM on August 9, 2015 [5 favorites]

Given input of the form 2^n 7^m where 0 ≤ m < n, the algorithm tries to divide n+1 by each number from n down to 1, until it finds the largest number k that is a divisor of n+1.

I guess I also don't understand how this is. I mean, why are you doing all this division? If it's odd, it's not a power of 2, and if it's even, you just find the log(2) of it, right? I mean, confirming that each number is prime is a lot of work, but if by some bizarre method this program can be guaranteed to produce primes, then just running it and listing outputs isn't that intensive, is it?
posted by kafziel at 6:54 PM on August 9, 2015

then 50 "encodes" 1,3,3. you can extract the "hidden" values by factoring the number: 50 = 2x5x5 and then working backwards from the position of the primes in the list: 2 -> 1, 5 -> 3, 5 -> 3.

Godel numbering is fun. I wrote a thing a while back that solves newspaper anagram puzzles and helps me cheat at Scrabble by converting words to a Godel numbering of their letter counts.

For example, "Woolloomooloo" might end up coded as 2¹×3⁸×5³×7¹ = 11481750; given the same coding, both "wool" and "loom" would then end up coded as 2¹×3²×5¹ = 90.

The nice properties of this encoding are that (a) it's insensitive to letter ordering and (b) if and only if the coding for one word is exactly divisible by that of another, the second word can be formed by selecting letters from the first one.
posted by flabdablet at 7:40 PM on August 9, 2015 [3 favorites]

That second property doesn't hold: even in your example you have two words with dissimilar letters that have the same encoding.
posted by Joe in Australia at 8:02 PM on August 9, 2015

That second property doesn't hold: even in your example you have two words with dissimilar letters that have the same encoding.

Yes. But what he wrote is not what he meant. And what he meant is correct.

It's funny how, when applying the above technique to understanding what people say, it turns out that people often say sensible things...
posted by brambleboy at 8:17 PM on August 9, 2015 [2 favorites]

two words with dissimilar letters that have the same encoding

How so?

Coding "Woolloomooloo" as 2¹×³⁸×⁵³×⁷¹ = 11481750 requires associating 2 with W, 3 with o, 5 with l and 7 with m. Applying the same encoding to "wool" gets you 2×3×3×5 = 90; to "loom" gets 5×3×3×2 = 90.

11481750 is exactly divisible by 90, so both "wool" and "loom" can be formed by selecting letters from "Woolloomooloo".

So can "loll" (375) and "moll" (525).
posted by flabdablet at 8:41 PM on August 9, 2015 [1 favorite]

...ah, I see. "wool" does indeed code to 90, but "loom" should code as 7×3×3×2 = 126. Apparently I can no longer tell the difference between a w and an m.

Anyway, the point is that all those small codes are factors of 11481750.
posted by flabdablet at 8:43 PM on August 9, 2015 [1 favorite]

whoa brambleboy, thank you.
posted by mrdaneri at 8:54 PM on August 9, 2015

...Game of Life. Someone wrote a version of that to run on my very first computer (~1977) - the RCA COSMAC VIP, an early single-board computer based on the CDP1802. I spent hours messing with that.

I think the most impressive GoL implementation I ever saw was Tomas Rokicki's one for the Amiga, which used the Amiga's blitting hardware to calculate the next Life generation in bulk instead of doing it cell by cell with the CPU.

These days, of course, that kind of thing is so much less remarkable that you can even do it in your browser.
posted by flabdablet at 10:13 PM on August 9, 2015

"loom" should code as 7×3×3×2 = 126

Aaargh! 5×3×3×7 = 315.

There's a reason I use computers for this kind of thing.
posted by flabdablet at 11:06 PM on August 9, 2015 [2 favorites]