Posted by 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:
1. Set *f* equal the first fraction in the list.
2. 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](http://scienceblogs.com/goodmath/2006/10/pathological_programming_ignor.php). 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](http://mathworld.wolfram.com/FRACTRAN.html)) 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.
October 27, 2006
October 27, 2006
October 27, 2006
October 27, 2006
October 27, 2006
October 27, 2006
October 27, 2006
October 27, 2006
October 28, 2006
October 28, 2006
October 28, 2006
October 29, 2006
October 29, 2006
October 30, 2006
November 3, 2006
April 18, 2007
December 4, 2007
March 10, 2010