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 (rational numbers), 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)+1$ 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]) in vector representation would be:

$$\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. It is also very easy to calculate the size of a rule or program in vector representation. It is the sum of absolute values of all elements in the matrix + number of rules (number of rows).

Champions

n	BBf(n)	Example Champion	Vector Representation
2	1	[1/2]	$\left[\begin{array}{c}-1\end{array}\right]$
3	1	[3/2]	$\left[\begin{array}{cc}-1& 1\end{array}\right]$
4	1	[9/2]	$\left[\begin{array}{cc}-1& 2\end{array}\right]$
5	2	[3/2, 1/3]	$\left[\begin{array}{cc}-1& 1\\ 0& -1\end{array}\right]$
6	3	[9/2, 1/3]	$\left[\begin{array}{cc}-1& 2\\ 0& -1\end{array}\right]$
7	4	[27/2, 1/3]	$\left[\begin{array}{cc}-1& 3\\ 0& -1\end{array}\right]$
8	5	[81/2, 1/3]	$\left[\begin{array}{cc}-1& 4\\ 0& -1\end{array}\right]$
9	6	[243/2, 1/3]	$\left[\begin{array}{cc}-1& 5\\ 0& -1\end{array}\right]$
10	7	[729/2, 1/3]	$\left[\begin{array}{cc}-1& 6\\ 0& -1\end{array}\right]$
11	10	[27/2, 25/3, 1/5]	$\left[\begin{array}{ccc}-1& 3& 0\\ 0& -1& 2\\ 0& 0& -1\end{array}\right]$
12	13	[81/2, 25/3, 1/5]	$\left[\begin{array}{ccc}-1& 4& 0\\ 0& -1& 2\\ 0& 0& -1\end{array}\right]$
13	17	[81/2, 125/3, 1/5]	$\left[\begin{array}{ccc}-1& 4& 0\\ 0& -1& 3\\ 0& 0& -1\end{array}\right]$
14	21	[243/2, 125/3, 1/5]	$\left[\begin{array}{ccc}-1& 5& 0\\ 0& -1& 3\\ 0& 0& -1\end{array}\right]$
15	28	[1/45, 4/5, 3/2, 25/3]	$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 2\end{array}\right]$
16	53	[1/45, 4/5, 3/2, 125/3]	$\left[\begin{array}{ccc}0& -2& -1\\ 2& 0& -1\\ -1& 1& 0\\ 0& -1& 3\end{array}\right]$
17	107	[5/6, 49/2, 3/5, 40/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 3& 0& 1& -1\end{array}\right]$
18	211	[5/6, 49/2, 3/5, 80/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 4& 0& 1& -1\end{array}\right]$
19	≳ 370	[5/6, 49/2, 3/5, 160/7]	$\left[\begin{array}{cccc}-1& -1& 1& 0\\ -1& 0& 0& 2\\ 0& 1& -1& 0\\ 5& 0& 1& -1\end{array}\right]$

Behavior of Champions

All champions up to BBf(14) have very simple behavior. They are all of the form: $[\frac{3^a}{2},\frac{5^b}{3},...\frac{p_n^z}{p_{n-1}},\frac{1}{p_n}]$ or in vector representation (limited to 5 primes):

$$\left[\begin{array}{ccccc}-1& a& 0& 0& 0\\ 0& -1& b& 0& 0\\ 0& 0& -1& c& 0\\ 0& 0& 0& -1& d\\ 0& 0& 0& 0& -1\end{array}\right]$$

These champions all apply the first rule until they've exhasted all 2s, the second rule until they've exhausted all 3s, etc. They have a runtime of $1+a+ab+abc+abcd+\cdots$ and size $2k+a+b+c+d+\cdots$ where k is the number of rules/primes used. This grows linearly for k=1 (BBf(5) to BBf(10)) and quadratically for k=2 (BBf(11) ot BBf(14)).