Today’s pathological language is based on a piece of work called Fractran by John Conway of game theory fame. It’s a really fascinating bugger; absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I’ve ever seen. It’s amazing that this is Turing complete. It’s not a real programming language in the sense of being able to write practical programs; it’s more of a simple theoretical computational model which has been implemented as a language.
It’s based on the idea of numbers as products of prime factors. As you should remember from elementary school, every number can be represented by a collection of prime numbers that, multiplied together, produce the number. For a few examples:
- 24 = 2×2×2×3, or 23×31
- 291 = 3×97
- 1800 = 5×5×3×3×2×2×2=52×32×23
Conway figured out that using something based on that concept, you can express any computable function using nothing but a list of positive fractions.
Every computation takes a single integer I as input, and operates by repeatedly doing the following:
- Set f equal the first fraction in the list.
- Set p=f*I
- If p is an integer, then set I=p, and go back to step 1.
- Otherwise, set f to the next fraction in the list, and go back to step 2.
When you get through the entire list without any of the multiplications producing an integer, then the computation halts.That, my friends, is Turing complete.
Let’s look at an example. How would you implement basic multiplication in Fractran?
385/13, 13/21, 1/7, 3/11, 7/2, 1/3
To make it a tad easier to follow, let’s factorize the numbers that form the fractions:
(7×11×5)/13, 13/(3×7), 3/11, 7/2, 1/3
How is this a multiplication program? If you take any integer I which is the product of 2a and 3b, then running it through here will produce the number 5a×b.
Let’s try it: take 24×33=432. It’ll be easiest to follow if we use the prime factorings.
- *I**=24×33; *f*=385/13. That won’t be an integer; 13 isn’t a factor of **I**.
- * *f*=13/(3×7). That won’t be an integer, because 7 isn’t a factor of **I**.
- * *f*=3/11. That won’t be an integer, because 11 isn’t a factor of **I**.
- * *f*=7/2. That will be an integer, 23×33×7.
- * **I**=23×33×7; *f*=385/13. Not a prime, because 13 isn’t a factor of **I**.
- * *f*=13/(3×7). That will be an integer; **I**=13×23×32.
- By now, you should have a basic feel for what’s going on, so I’m going to start skipping the steps where **I**×*f* is not an integer.
- * *f*=385/13, **I** becomes 7×11×5×23×32/sup>
- * *f*=13/(3×7), **I** becomes 13×11×5×23×3.
- * *f*=(7×11×5)/13, **I** becomes 7×112×52×23×3.
- * *f*=13/(3×7), **I** becomes 13×112×52×23.
- * *f*=(7×11×5)/13, **I** becomes 7×113×53×23.
It keeps going like that. Let’s analyze it to see what’s really going on.
- the 7/2 fraction swaps a factor of 2 for a factor of 7. That’s basically removing a factor of two, which means subtracting 1 from *a*; and then adding in the 7 is keeping track of the fact that we haven’t yet added *b* to the result to match the subtraction of 1 from *a*.
- The 13/(3×7) rule allows us to start the process of adding *b* to the result. It removes one three, and the placeholder that says we subtracted one from *a*; and adds in a placeholder to say that we’ve removed one three, but haven’t finished adding.
- the (7×11×5)/13 rule says that if we’ve removed a three, we can add one to the exponent of five; and then we also need to add placeholders to continue the addition: we’ve adding one to the result, but we need to add *b* to the result. So we’re effectively subtracting one from *b* in order to keep track of the fact that we’ve done that much of an addition of *b* to the result.
- 3/11 says that if the first two rules didn’t work, then we’ve finished an addition, we we want to re-add 1 to *b*, in order to restore it to its original value. The other rules have added one 11 for each time we subtracted one from *b*, so this will restore *b*.
- Finally, if get get to the 1/3 rule, it means that we’ve removed all of the 2s, which means we’ve completed the multiplication. So we want to remove the *b* leaving the result.
Why is this turing complete? It should be pretty easy to see, once you get a sense of what’s going on. Prime numbers are basically variables – each prime number holds an integer value (its exponent). The factors of the denominators do two things: subtract values from a variable, and operate as statement guards determining what statements are executable. In terms of control flow, the end result is something that’s actually quite similar to Version. The primes that aren’t really being used as variables are the complement of the “ignore” set.
Evil, huh?
While researching this post, I discovered (via mathworld) that Conway figured out a way of writing
an astonishing prime number generator in Fractran. If you take the following sequence as a fractran program, in the numbers that it generates, the exponent on 2 in every number that it generates will always be prime.
17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1
Definitely the most incomprehensible prime number generator that I’ve ever seen.
Extremely cool! Thanks.
Looks like you dropped the 1/7 (the third fraction) at some point in the multiplication program. As I just discovered, it doesn’t work so well without it.
MarkCC wrote:
That, my friends, is my head exploding.
Since it is not bound strictly to base 2, I wonder what sort of machines could implement computation such as this. I’m hoping for something bizarre. 🙂
That’s quite a find, well done!
What Fractran and a lot of the other bizarre languages you’ve posted about point to is just how abstract a concept computation is. You choose your symbols and provide some rules for manipulating them and, if you can in some sense assign, add and loop you’ve got yourself a Turing complete language.
My god… that’s GENIUS! John Conway is insane in a wonderful way. Now that I’ve thought through it, it’s fairly obvious that it’s Turing-complete – it’s got an arbitrary number of data stacks which can hold any integer, and an arbitrary number of control states.
It’s just the idea of using multiplication to handle it which is astounding. Plus, essentially using a variant of Godel-numbering to encode the current program state in I.
I don’t know why this isn’t intended for serious (pathological) programming. It’s easier to program than a Turing machine. Hell, it’s easier to program than Brainfuck! I mean, the registers are arbitrarily addressable – no need to use all the < or > to select the register you want to operate on. Plus, you can encode several steps in a single operation.
Come to think of it, this may in fact be one of the easiest languages to program in that you’ve posted so far. It’s obviously not useful in a realistic context, any more than any pathological language is, but of all the languages so far it’s one of the easiest to use, imo.
Okay, I want to explain it now. It took me a bit to understand it, so I think I have an explanation of how it works that should be *extremely* simple and easy to understand. Plus, it illustrates why it is Turing-complete very clearly.
Like most simple languages, Fractran has two clearly defined spaces, one for data and one for instructions.
The data is stored in a series of registers, which each can store an integer value.
The instructions are stored as a list, and are all formed by the following statement:
IF(registers X, Y, Z are all non-zero)
THEN(decrement registers X, Y, Z (possibly multiple times); increment registers P, Q, R (possibly multiple times); go to label “begin”)
The program itself is always of the following form:
LABEL: begin
instruction1
instruction2
instruction3
etc.
END PROGRAM
This is a pretty simple idea, and fairly easy to program in. It just so happens that the registers are stored with a variant on Godel-numbering, where each register is represented by raising a corresponding prime to the register’s value and then they’re all multiplied together into I. And the instructions are represented as fractions, where registers X, Y, and Z are primes in the denominator and registers P, Q, and R are primes in the numerator. If you want to increment/decrement more than once, just put the primes in there multiple times.
Sound good?
I encountered this cool bit in Conway’s Book of Numbers, an excellent book to have on your shelf, full of little morsels like this. I wrote a couple of tiny programs to demonstrate how this works, but my trackback to this post didn’t seem to work. So, I’ll just point you at:
http://brainwagon.org/archives/2006/10/27/2207/
Which includes a simple Python implementation, as well as an interesting obfuscated C .signature program that might be amusing to stare at.
I was in Stockholm as Conway came to visit for a youth mathematical conference and gave a lecture at the local research seminar in connection to it.
He came into a seminar room, wrote that last sequence on the board, and continued to produce the first three-four primes by executing the program.
And then went on to discuss Turing-completeness, where the complexity and other theoretical computer science problems were hidden away.
Why yes, I think Conway is the single most captivating mathematical lecturer I have ever seen. There was a time when I dreamed about going to Princeton to do my PhD with him.
After just *doing* it, I realized another bonus of this language – how very, very simple it is to write an interpreter for. I did it in 5 pretty-printed lines in Lisp. ^_^
I need to add a quick debug facility that will step through it and return I at each step, so you can actually run Conway’s prime generator.
Wonderful! Simply wonderful! That makes three of my favourite things that were invented (or perhaps *discovered*) by John Conway: this, Life, and Surreal Numbers. My homework for tonight is to step through that generator and see how it works.
P.S. Isn’t it about time that INTERCAL was featured here, I believe it is the forerunner of deliberately pathological languages, and the specification is a joy to behold.
Xanthir:
You explanation got it exactly – a much clearer explanation of it than I managed.
The reason that I said it’s not really a programming language is because there’s no plausible way of adding things like IO to it, to allow it to be used for real programs, without totally ruining it. But it is one of the most amazingly beautiful basic computing models that I’ve ever seen. It’s certainly more elegant and beautiful than the Turing machine, which is incredibly complicated and hard to follow in comparison.
This thread is dual to the thread on number bases.
To extraterrestrials who notate numbers by their prime factorization, for instance superimposing icons of the primes involved, multiplication is trivial. Simply superimpose the icons of the two integers being multiplied. On the other hand, addition would be very computationally difficult, with the aliens having to memorize and/or consult addition tables.
Their equivalent of Euclid or Archimedes would have been homomorphic to our Turing. They’d have invented public key cryptosystems (30 years old for us, yesterday) before they invented the steam engine. Their steam engine, by the way, would be to power their Babbage Analytical Engine, which would have been like Turing’s electromaechanical Reimann Hypothesis checker.
http://blogs.zdnet.com/BTL/?p=3847
Cryptos gather for 30th anniversary of public-key cryptography Posted by Dan Farber @ 11:55 am
27 Oct 2006
The 26 sporadic groups are are often written in the same type of prime notation.
Conway is credited with a few of these groups.
http://mathworld.wolfram.com/SporadicGroup.html
Is there a relationship beyond Conway’s name?
How do you do an infinite loop? You could use the sequence:
1
but it feels like cheating, because it isn’t a nice fraction.
Conway also did a good deal of interesting work on lattices and coding (see e.g. Conway + Sloane’s seminal reference). He also did some stuff with 4D polytopes, which is (are?) a lot of fun.
“absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I’ve ever seen.”
Oh, so it’s like Haskell, then?
😉
I realize this is old, but to address the infinite loop query, here’s a short “program” that does exactly that:
Input = 2
fraction list: 3/2 2/3
Although this trivial example has two inverses together, inverses (or any set of fractions that when multiplied together produce 1) don’t necessarily result in infinite loops. Consider:
Input = a
fractions: 1/b a/b b/a
For any combination of a and b where a and b are relatively prime this will terminate. On the other hand, if the fraction list were reversed it would NOT terminate.
… very interesting language.
I believe that the real beauty of Conway’s Fractran prime number generator is that not only is the exponent of 2 a prime number whenever the output is of the form 2^n, but that these exponents run through the complete set of prime numbers in ascending order. If my understanding is correct, can someone explain why/how this remarkable prime number sieve works?
Since Fractran is Turing-complete, it must be able to implement the identity function, right? But how do you do this in Fractran? It seems for any program considered for identity there is always an input that results in a different output: use the denominator of one of the fractions is as input. Is there some other particular mapping between inputs and outputs that would be considered identity?
Maybe I’m misunderstanding Turing-completeness?