View source for Fractran

'''Fractran''' (originally styled FRACTRAN) is an esoteric Turing complete model of computation invented by John Conway in 1987.<ref>Conway, John H. (1987). "FRACTRAN: A Simple Universal Programming Language for Arithmetic". ''Open Problems in Communication and Computation''. Springer-Verlag New York, Inc. pp. 4–26. <nowiki>http://doi.org/10.1007/978-1-4612-4808-8_2</nowiki></ref> 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 <math>[q_0, q_1, ... q_{k-1}]</math>called rules and a fractran state is an integer <math>s \in \mathbb{Z}</math>. We say that a rule <math>q_i</math> applies to state <math>s</math> if <math>s \cdot q_i \in \mathbb{Z}</math>. 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 <math>s \to t</math> and <math>t = s \cdot q_i</math> and <math>i = \min \{ i : s \cdot q_i \in \mathbb{Z} \}</math>. As with [[Turing machines]], we will write <math>s \xrightarrow{N} t</math> if <math>s \to s_1 \to \cdots \to s_{N-1} \to t </math> (s goes to t after N steps) and <math>s \to^* t</math> or <math>s \to^+ t</math> if <math>s \xrightarrow{N} t</math> for some N≥0 or N≥1 (respectively). We say that a program has runtime N (or halts in N steps) starting in state s if <math>s \xrightarrow{N} t</math> and computation halts on t.

Let <math>\Omega(n)</math> be the total number of prime factors of a positive integer n. In other words, <math>\Omega(2^{a_0} 3^{a_1} \cdots p_n^{a_n}) = \sum_{k=0}^n a_n</math>. Then given a rule <math>\frac{a}{b} </math> we say that  <math>\text{size} \left( \frac{a}{b} \right) = \Omega(a) + \Omega(b) </math>. And the size of a fractran program <math>[q_0, q_1, ... q_{k-1}]</math> is <math>k + \sum_{i=0}^{k-1} \text{size}(q_i) </math>.

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 <math>[ a_0, a_1, \dots, a_{n-1} ] \in \mathbb{Z}^n</math> to represent the number <math>2^{a_0} 3^{a_1} \cdots p_{n-1}^{a_{n-1}}</math>.

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

Now, rule q applies to state s iff <math>v(s) + v(q) \in \mathbb{N}^n</math> (all components of the vector are ≥0) and if <math>s \to t</math> then <math>v(t) = v(s) + v(q)</math>. 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 (<code>[1/45, 4/5, 3/2, 25/3]</code>) in vector representation would be:

<math display="block">\begin{bmatrix}
   0 & -2 & -1 \\
   2 &  0 & -1 \\
  -1 &  1 &  0 \\
   0 & -1 &  2
\end{bmatrix}</math>

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 ==
{| class="wikitable"
|+
!n
!BBf(n)
!Example Champion
!Vector Representation
|-
| 2 || 1 || <code>[1/2]</code>
|<math>\begin{bmatrix}
  -1
\end{bmatrix}</math>
|-
| 3 || 1 || <code>[3/2]</code>
|<math>\begin{bmatrix}
  -1 & 1
\end{bmatrix}</math>
|-
| 4 || 1 || <code>[9/2]</code>
|<math>\begin{bmatrix}
  -1 & 2
\end{bmatrix}</math>
|-
| 5 || 2 || <code>[3/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  1 \\
   0 & -1
\end{bmatrix}</math>
|-
| 6 || 3 || <code>[9/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  2 \\
   0 & -1
\end{bmatrix}</math>
|-
| 7 || 4 || <code>[27/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  3 \\
   0 & -1
\end{bmatrix}</math>
|-
| 8 || 5 || <code>[81/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  4 \\
   0 & -1
\end{bmatrix}</math>
|-
| 9 || 6 || <code>[243/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  5 \\
   0 & -1
\end{bmatrix}</math>
|-
| 10 || 7 || <code>[729/2, 1/3]</code>
|<math>\begin{bmatrix}
  -1 &  6 \\
   0 & -1
\end{bmatrix}</math>
|-
| 11 || 10 || <code>[27/2, 25/3, 1/5]</code>
|<math>\begin{bmatrix}
  -1 &  3 &  0 \\
   0 & -1 &  2 \\
   0 &  0 & -1
\end{bmatrix}</math>
|-
| 12 || 13 || <code>[81/2, 25/3, 1/5]</code>
|<math>\begin{bmatrix}
  -1 &  4 &  0 \\
   0 & -1 &  2 \\
   0 &  0 & -1
\end{bmatrix}</math>
|-
| 13 || 17 || <code>[81/2, 125/3, 1/5]</code>
|<math>\begin{bmatrix}
  -1 &  4 &  0 \\
   0 & -1 &  3 \\
   0 &  0 & -1
\end{bmatrix}</math>
|-
| 14 || 21 || <code>[243/2, 125/3, 1/5]</code>
|<math>\begin{bmatrix}
  -1 &  5 &  0 \\
   0 & -1 &  3 \\
   0 &  0 & -1
\end{bmatrix}</math>
|-
| 15 || 28 || <code>[1/45, 4/5, 3/2, 25/3]</code>
|<math>\begin{bmatrix}
   0 & -2 & -1 \\
   2 &  0 & -1 \\
  -1 &  1 &  0 \\
   0 & -1 &  2
\end{bmatrix}</math>
|-
| 16 || 53 || <code>[1/45, 4/5, 3/2, 125/3]</code>
|<math>\begin{bmatrix}
   0 & -2 & -1 \\
   2 &  0 & -1 \\
  -1 &  1 &  0 \\
   0 & -1 &  3
\end{bmatrix}</math>
|-
| 17 || 107 || <code>[5/6, 49/2, 3/5, 40/7]</code>
|<math>\begin{bmatrix}
   -1 & -1 &  1 &  0 \\
   -1 &  0 &  0 &  2 \\
    0 &  1 & -1 &  0 \\
    3 &  0 &  1 & -1
\end{bmatrix}</math>
|-
| 18 || 211 || <code>[5/6, 49/2, 3/5, 80/7]</code>
|<math>\begin{bmatrix}
   -1 & -1 &  1 &  0 \\
   -1 &  0 &  0 &  2 \\
    0 &  1 & -1 &  0 \\
    4 &  0 &  1 & -1
\end{bmatrix}</math>
|-
| 19 || ≳ 370 || <code>[5/6, 49/2, 3/5, 160/7]</code>
|<math>\begin{bmatrix}
   -1 & -1 &  1 &  0 \\
   -1 &  0 &  0 &  2 \\
    0 &  1 & -1 &  0 \\
    5 &  0 &  1 & -1
\end{bmatrix}</math>
|}

=== Behavior of Champions ===

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

<math display="block">\begin{bmatrix}
   -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{bmatrix}</math>

These champions apply repeatedly apply the rules in sequence, never going back to a previous rule. They apply the first rule until they've exhausted all 2s, then the second rule until they've exhausted all 3s, etc. They have a runtime of <math>1 + a + ab + abc + abcd + \cdots</math> and size <math>2k + a + b + c + d + \cdots</math> 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)).

==== BBf(17) Family ====
The BBf(17) to BBf(19) champions are members of a family of programs (parameterized by <math>m,n \ge 0</math>)

<math display="block">\begin{bmatrix}
   -1 & -1 &  1 &  0 \\
   -1 &  0 &  0 &  n \\
    0 &  1 & -1 &  0 \\
    m &  0 &  1 & -1
\end{bmatrix}</math>

which have size <math>m+n+12</math>

This family obeys the following rules:

# <math>[1, 0, 0, 0] \xrightarrow{1} [0, 0, 0, n]</math>
# if d≥1 and b≤m:<math>[0, b, 0, d] \xrightarrow{m+b+2} [0, b+1, 0, d - 1 + n(m-b)]</math>
# if d≥1 and b≥m:<math>[0, b, 0, d] \xrightarrow{2m+2} [0, b+1, 0, d - 1]</math>
#if d=0: [0,b,0,d] has halted

and furthermore these rules are applied in order since b is always increasing (and d is eventually decreasing). Combining these together we get runtime:<math display="block">1 + n(m+1)(m(m+1)+2) - \frac{m(m+1)}{2}</math>

The optimal choices for n,m for various program sizes are:
{| class="wikitable"
|+
!Size
!n
!m
!Runtime
|-
|16
|1
|3
|51
|-
|17
|2
|3
|107
|-
|18
|2
|4
|211
|-
|19
|2
|5
|370
|-
|20
|2
|6
|596
|-
|21
|3
|6
|904
|}

== References ==
<references />