Fractran: Difference between revisions

Revision as of 21:04, 10 November 2025

Fractran (originally styled FRACTRAN) is an esoteric Turing complete model of computation invented by John Conway in 1987.^[1] 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 ℤ$ . We say that a rule $q_{i}$ applies to state $s$ if $s \cdot q_{i} \in ℤ$ . 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 ℤ}$ . We say that a program has runtime N (or halts in N steps) starting in state s if $s \to s_{1} \to \dots \to s_{N}$ and no rule applies to $s_{N}$ .

Let $Ω (n)$ be the total number of prime factors of a positive integer n. In other words $Ω (1) = 0$ and $Ω (p n) = Ω (n)$ for any prime number p. Then given a rule $\frac{a}{b}$ we say that $size (\frac{a}{b}) = Ω (a) + Ω (b)$ . And the size of a fractran program $[q_{0}, q_{1}, . . . q_{k - 1}]$ is $k + \sum_{i = 0}^{k - 1} 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.

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]`

References

↑ 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. http://doi.org/10.1007/978-1-4612-4808-8_2

[1] 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. http://doi.org/10.1007/978-1-4612-4808-8_2

[1]

@@ Line 1: / Line 1: @@
-'''Fractran''' (originally styled FRACTRAN) is an esoteric 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, the program state is an integer. For more details see https://en.wikipedia.org/wiki/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, 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. Specifically, it is the longest runtime for all halting fractran programs of size n when started with state = 2. In this context we consider the size of a fractran program to be the total number of fractions plus the total number of prime factors (counting multiplicity) of all numerators and denominators of all fractions.
+'''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>. We say that a program has runtime N (or halts in N steps) starting in state s if <math>s \to s_1 \to \cdots \to s_N </math> and no rule applies to <math>s_N </math>.
+Let <math>\Omega(n)</math> be the total number of prime factors of a positive integer n. In other words <math>\Omega(1) = 0</math> and <math>\Omega(pn) = \Omega(n)</math> for any prime number p. 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.
 == Champions ==
@@ Line 14: / Line 21: @@
 | 2 || 1 || <code>[1/2]</code>
 |-
-| 3 || 1 || <code>[1/2]</code>
+| 3 || 1 || <code>[3/2]</code>
 |-
-| 4 || 1 || <code>[1/2]</code>
+| 4 || 1 || <code>[9/2]</code>
 |-
 | 5 || 2 || <code>[3/2, 1/3]</code>

Fractran: Difference between revisions

Revision as of 21:04, 10 November 2025

Definition

Champions

References

Navigation menu

Search