Fractran

Fractran (originally styled FRACTRAN) is an esoteric Turing complete model of computation invented by John Conway in 1987. In this model a program is simply a finite list of fractions, the program state is an integer. For more details see https://en.wikipedia.org/wiki/FRACTRAN

BB_fractran(n) or BBf(n) is the Busy Beaver function for Fractran programs.

Definition

A fractran program is a list of rational numbers $[q_0,q_1,...q_{k-1}]$called rules and a fractran state is an integer $s\in \mathbb{\mathbb{Z}}$. We say that a rule $q_i$ applies to state $s$ if $s\cdot q_i\in \mathbb{\mathbb{Z}}$. If no rule applies, we say that the computation has halted otherwise we apply the first applicable rule at each step. In that case we say $s\to t$ and $t=s\cdot q_i$ and $i=\min \{i:s\cdot q_i\in \mathbb{\mathbb{Z}}\}$. We say that a program has runtime N (or halts in N steps) starting in state s if $s\to s_1\to \cdots \to s_N$ and no rule applies to $s_N$.

Let $\mathrm{\Omega }(n)$ be the total number of prime factors of a positive integer n. In other words $\mathrm{\Omega }(1)=0$ and $\mathrm{\Omega }(pn)=\mathrm{\Omega }(n)$ for any prime number p. Then given a rule $\frac{a}{b}$ we say that $\text{size}\left(\frac{a}{b}\right)=\mathrm{\Omega }(a)+\mathrm{\Omega }(b)$. And the size of a fractran program $[q_0,q_1,...q_{k-1}]$ is $k+\sum _{i=0}^{k-1}\text{size}(q_i)$.

BB_fractran(n) or BBf(n) is the maximum runtime starting in state 2 for all halting fractran programs of size n. It is a non-computable function akin to the Busy Beaver Functions since Fractran is Turing Complete.

Vector Representation

Fractran programs are not easy to interpret, in fact it may be completely unclear at first that they can perform any computation at all. One of the key insights is to represent all numbers (states and rules) in their prime factorization form. For example, we can use a vector $[a_0,a_1,\dots ,a_{n-1}]\in {\mathbb{\mathbb{Z}}}^n$ to represent the number $2^{a_0}{3}^{a_1}\cdots p_{n-1}^{a_{n-1}}$.

Let the vector representation (for a sufficiently large n) for a state $a=2^{a_0}{3}^{a_1}\cdots p_{n-1}^{a_{n-1}}$ be $v(a)=[a_0,a_1,\dots ,a_{n-1}]\in {\mathbb{\mathbb{N}}}^n$ and the vector representation for a rule $\frac{a}{b}$ be $v\left(\frac{a}{b}\right)=v(a)-v(b)\in {\mathbb{\mathbb{Z}}}^n$ (Note that this is just an extension of the original definition extended to allow negative $a_i$).

Now, rule q applies to state s iff $v(s)+v(q)\in {\mathbb{\mathbb{N}}}^n$ (all components of the vector are ≥0) and if $s\to t$ then $v(t)=v(s)+v(q)$. So the fractran multiplication model is completely equivalent to the vector adding model. For presentation, we will represent a fractran program with a matrix where each row is the vector representation for a rule.

For example, the BBf(15) champion ([1/45, 4/5, 3/2, 25/3]) would be represented as:

$$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 2\\ \end{array}\right]$$

In this representation, it becomes much easier to reason about fractran programs and describe general rules.

Champions

n	BBf(n)	Example Champion(s)
1	0	[1/1]
2	1	[1/2]
3	1	[3/2]
4	1	[9/2]
5	2	[3/2, 1/3]
6	3	[9/2, 1/3]
7	4	[27/2, 1/3]
8	5	[81/2, 1/3]
9	6	[243/2, 1/3]
10	7	[729/2, 1/3]
11	10	[27/2, 25/3, 1/5]
12	13	[81/2, 25/3, 1/5]
13	17	[81/2, 125/3, 1/5]
14	21	[243/2, 125/3, 1/5]
15	28	[1/45, 4/5, 3/2, 25/3]
16	53	[1/45, 4/5, 3/2, 125/3]
17	107	[5/6, 49/2, 3/5, 40/7]
18	211	[5/6, 49/2, 3/5, 80/7]
19	≳ 370	[5/6, 49/2, 3/5, 160/7]