fractran

A game invented by John Conway. Or a programming language, if you prefer.

A fractran program/game/instance is given as a list of rational numbers q₁, q₂,...,q_k. You start with some integer x₀ and each subsequent x_i+1 is given by x_i+1=q_jx_i, where q_j is the first number in the sequence such that q_jx_i is an integer. Computation proceeds until no such number can be found in the sequence.

It's a very simple model of computation, in the sense of having very few instructions, and rather surprisingly it can be shown that fractran can compute any computable function.

The classic (only?) example of a fractran program is

17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1

which can compute prime numbers: you start with x₀=2, and any power of 2 that occurs in the computation is 2^p where p is a prime number.

I've found in a web page (http://www.maths.uwa.edu.au/seminars/1999/Pure/13.html) another, shorter, prime-calculating program:

7/3 99/98 13/49 39/35 36/91 10/143 49/13 7/11 1/2 91/1

which uses x₀=10 and shows primes as powers of ten.