FRACTRAN

[twinb7]

What always interested me about cellular automata was creating large computational structures using simple rules. In that spirit is FRACTRAN, a simple game with fractions invented(?popularized?) by John Conway.

A FRACTRAN program consists of a list of fractions f1, f2, f3... fN and an input value Z. For the first fraction f in the list for which f*Z is an integer, replace Z with f*Z. Halt when there is no such fraction.

Amazingly, this process is capable of universal computation. It functions like a register machine where the exponents in the prime factorization of Z are the values in various registers. The 'division' allows a test-dec command. For example, the program

Code: Select all

2/3

when given a value of (2^a)(3^b) returns a value of (2^a+b).

More complicated programs follow: This one starts with Z=2 and eventually gives Z=2^3, 2^5, 2^7, 2^11... generating the prime numbers.

Code: Select all

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

This is a program I created myself - when given 2^a it returns 2^(a/2) if a is even and 2^(3a+1) if a is odd and repeats, calculating a Collatz sequence.

Code: Select all

832/33
16/11
11/13
14/15
1/5
5/7
3/4
11/2
10/3