FRACTRAN

Some of my favourite books were written by Douglas Adams. (Indeed, my forename was actually named after his surname, rather than my Biblical namesake or the Greek word for ‘indestructible’.) Although I personally prefer the Dirk Gently books, I have to say that one of my favourite quotes is from the Hitchhiker’s Guide to the Galaxy:

It was on display in the bottom of a locked filing cabinet stuck in a disused lavatory with a sign on the door saying ‘Beware of the Leopard’

This reminds me of how a particularly insightful 20-year-old e-mail from John Conway is ‘on display’ in the password-protected archives of an obscure mailing list. Rather interestingly, the e-mail originated from speculation as to whether gliders are possible on a Penrose tiling. It took almost two decades for this question to be answered (in the affirmative), after the question was raised independently by Andrew Trevorrow and Tim Hutton.

[youtube=http://www.youtube.com/watch?v=6xVLpP25DRQ]

Conway recounts how he had considered automata on Penrose tilings, but subsequently rejected them in favour of simpler Turing-complete models of computation. One of his ideas was for a universal system that changes its topology, rather like how neurones in the human brain can connect, separate and reproduce with miraculous results. Some very early work in this area was by Alan Turing himself, described in The Emperor’s New Mind and summarised here.

A ‘full adder’, a basic arithmetical circuit, composed entirely of NAND gates

Basically, Turing reasoned that since NAND gates are capable of arbitrary finite computations, such as basic arithmetic, then in a very large, random mass of interconnected NAND gates, it might be possible for intelligence to arise. He referred to these as A-type machines.

However, in the human brain, connections are continually made and broken. He added extra provision (a ‘connection modifier’), resulting in the concept of a B-type machine. Of course, the connection modifiers themselves can be built from NAND gates, so there is no need to physically make and break connections.

Conway’s idea was more abstract than this, involving a (multi?)graph that evolves according to specific, local rules. I think that the closest realisation of this was Hiroki Sayama’s Generative Network Automata, although I am unaware whether any further developments have been made in this area.

Even simpler systems

At the moment, the candidates for ‘simplest universal system’ include Rule 110, a one-dimensional cellular automaton proved universal by Matthew Cook, Alex Smith’s 2-symbol 3-state Turing machine, and the SK combinator calculus. There’s an even simpler system (a Post-tag system), but it is not known whether or not it’s capable of universal computation.

Of course, the universality of Alex Smith’s Turing machine was discovered 14 years after Conway’s e-mail, which continues:

    This reminds me of my Jugendtraum, which is to find a still simpler kind of universal system that just plays one game with an infinite deck of numbered cards, and can be programmed just by suitably stacking the cards.  The rules are simple – eg., if you see a card numbered n, move n places right and reverse the order of the cards you move over (and maybe negate them).  [negative n are allowed]

It’s important that whatever the rule is, there’s only one of it – the “machine” that plays this game doesn’t have a varying “state”.  But somehow this simple rule can be programmed to compute any computable function of m,n,… just by starting it at a,b,c,…,m,n,…  for a suitable finite string a,b,c,…  (the program).

I got some rather messy rules, but still think that there should be a simple one.  The dream is that “the nice rule” is more or less unique, and astonishingly simple, and leads to a complete reformulation of the theory of computable functions.

Whilst none of the results of this search satisfied him, a few beautiful fruits grew out of this ambition. One of these was Conway’s Game of Life, which grew extraordinarily popular during the 1970s thanks to a column by Martin Gardner in the Scientific American magazine.

FRACTRAN

The other, which I’m going to mention here, was a truly remarkable ‘programming language’ called FRACTRAN. The current state of the automaton is an integer, N, and the transition rules are a list of fractions. For example, one of Conway’s programs begins with N = 2 and has the following fourteen transition rules:

On each step, multiply N by the first fraction that results in an integer. In this case, we multiply it by \dfrac{15}{2} to give N = 15. Then we multiply it by \dfrac{55}{1}, giving N = 825, since none of the others gives an integer. Now we can multiply it by \dfrac{29}{33} to give N = 725. The first few integers obtained are as follows:

2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170,
156, 132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875,
25375, 67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620,
4060, 10780, 12740, 2380, 2184, 408, 152, 92, 380, 230, 950, 575,
2375, 9625, 11375, 2125, 1950, 1650, 1450, 3850, 4550, 850, 780,
660, 580, 1540, 1820, 340, 312, 264, 232, 616, 728, 136, 8, 60,
...

If we run it for longer and look at the powers of two that appear, we get {2, 4, 8, 32, 128, 2048, …}. Ignoring the initial 2, these are precisely 2^p for prime p. In other words, this sequence of fractions computes prime numbers! This may seem miraculous, and indeed it is impressive, but the underlying mathematics is actually quite banal.

Note that we’re working with just the multiplicative structure of the integers, and don’t care about the additive structure. In this format, it is most convenient to consider only the prime factorisation of the fractions. Shown below are the exponents in the prime factorisations of the first few fractions.

  • 17/91 –> (0, 0, 0, -1, 0, -1, 1, 0, 0, 0)
  • 78/85 –> (0, 1, -1, 0, 0, 1, -1, 0, 0, 0)
  • 19/51 –> (0, -1, 0, 0, 0, 0, -1, 1, 0, 0)

Essentially, FRACTRAN uses each of the exponents in the prime factorisation of N as registers to store nonnegative integers, and the fractions increment and decrement the registers according to whether or not they are empty. In this way, it behaves as a counter machine, the same model of computation I used to prove the Turing-completeness of three-dimensional chess.

He wrote two other programs, a universal computer with just 21 fractions and a 38-fraction machine for generating the decimal expansion of pi. The latter (avaliable here, although apparently slightly erroneous) is massively inefficient, using Wallis’ product. Conway also provided an initial value of N to instruct the universal 21-fraction machine to emulate the 38-fraction machine…

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to FRACTRAN

  1. wojowu says:

    I’m pretty sure Tag systems are universal. There is 50 years old paper by Cooke and Minsky estabilishing this result: http://dspace.mit.edu/bitstream/handle/1721.1/6107/AIM-052.pdf?sequence=2

    • apgoucher says:

      Tag systems are universal in *general*. The open problem is whether the *specific* Tag system with substitution rules 0xxS –> S00 and 1xxS –> S1101 is universal (all simpler ones are certainly decidable).

Leave a Reply