| \(c\) | All defined values of \(f_c\) |
|---|---|
| 0 | none |
| 1 | \(n\rightarrow n\) |
| 2 | \(0\rightarrow 1\) |
| 4 | \(0\rightarrow 2\) |
| 8 | \(1\rightarrow 2\) |
| 16 | \(2\rightarrow 3\) |
| 64 | \(1\rightarrow 3\) |
| 77 | \(n\rightarrow 0\) |
| 128 | \(0\rightarrow 3\) |
| 133 | \(0\rightarrow 0\) |
| 255 | \(n+1\rightarrow n+1\) |
| 256 | \(3\rightarrow 4\) |
| 847 | \(n\rightarrow 1\) |
| 37,485 | \(0\rightarrow 0, n+1\rightarrow n\) |
| 2,268,945 | \(n\rightarrow n+1\) |
| \(2^{2^{b}-2^{a}}\) | \(a\rightarrow b\) |
| \(7\cdot 11^{2^{k}}\) | \(n\rightarrow k\) |
| \(\frac{15}{7}\cdot 1,029^{2^{k-1}}\) | \(n\rightarrow n+k\) |
| \(c_\pi\) | \(n\rightarrow n\)th digit of \(\pi\) |
FRACTRAN is an esoteric Turing-complete language devised by John Conway,[1] based on Marvin Minsky's formalized register machines.[2] Conway devised a universal FRACTRAN program called POLYGAME, which give rise to catalogue numbers that map to all possible computable partial functions. For many well-known functions, catalogue numbers are not difficult to devise, and tend to be quite large numbers.
Description[]
A Fractran-1 program is a tuple of fractions \((f_1,\ldots,f_n)\). A Fractran interpreter has an internal state which is a positive integer \(N\). Its initial state is considered the input to the program. The program is executed by repeating the following process: find the first \(f_i\) in the program such that \(Nf_i\) is an integer, then set \(N\) to \(Nf_i\). If no matching fraction is found, the program halts, and the final value of \(N\) is the output of the program.
The exponents of the prime factors of \(N\) serve as registers, and a fraction \(\frac{p^{a}}{q^{b}}\) (with \(p,q\) prime) serves as the instruction to increment register \(p\) by \(a\) and decrement register \(q\) by \(b\).
Example programs[]
Conway gives three "free samples" of Fractran programs: PRIMEGAME, which lists the primes, PIGAME, which gives the \(n\)th digit of \(\pi\), and a universal program POLYGAME:
- \(\frac{583}{559}\, \frac{629}{551}\, \frac{437}{527}\, \frac{82}{517}\, \frac{615}{329}\, \frac{371}{129}\, \frac{1}{115}\, \frac{53}{86}\, \frac{43}{53}\, \frac{23}{47}\, \frac{341}{46}\)
- \(\frac{41}{43}\, \frac{47}{41}\, \frac{29}{37}\, \frac{37}{31}\, \frac{299}{29}\, \frac{47}{23}\, \frac{161}{15}\, \frac{527}{19}\, \frac{159}{7}\, \frac{1}{17}\, \frac{1}{13}\, \frac{1}{3}\)
for which he proved the following:
Theorem. Define \(f_c(n) = m\) if POLYGAME, given input \(c2^{2^{n}}\), outputs \(2^{2^{m}}\), and otherwise leave \(f_c(n)\) undefined. Then every computable function appears among \(f_0, f_1, f_2\, \cdots\)
Conway calls these indices \(c\) the "catalogue numbers", and remarks that they "are easily computable for some quite interesting functions". As an example, he gives an integer \(c_\pi\) such that \(f_{c_\pi}(n)\) is the \(n\)th digit of \(\pi\).
- \(c_\pi = 3^{A}\cdot 5^{2^{89\cdot101!}+2^{90\cdot101!}}\cdot 17^{101!-1}\cdot 23\) where \(A=2^{100!}+\sum_{i=1}^{38}2^{f_i\cdot101^{i}\cdot100!}+2^{101^{39}\cdot100!}\)
and the thirty-eight \(f_i\)'s are the fractions in this version of PIGAME:
- \(\frac{365}{46}\, \frac{29}{161}\, \frac{79}{575}\, \frac{7}{451}\, \frac{3,159}{413}\, \frac{83}{497}\, \frac{473}{371}\, \frac{638}{355}\, \frac{434}{335}\, \frac{89}{235}\, \frac{17}{209}\, \frac{79}{122}\, \frac{31}{183}\, \frac{41}{115}\, \frac{517}{89}\, \frac{111}{83}\, \frac{305}{79}\)
- \(\frac{23}{73}\, \frac{73}{71}\, \frac{61}{67}\, \frac{37}{61}\, \frac{19}{59}\, \frac{89}{57}\, \frac{41}{53}\, \frac{883}{47}\, \frac{53}{43}\, \frac{86}{41}\, \frac{13}{38}\, \frac{23}{37}\, \frac{67}{31}\, \frac{71}{29}\, \frac{83}{19}\, \frac{475}{17}\, \frac{59}{13}\, \frac{41}{3}\, \frac{1}{7}\, \frac{1}{11}\, \frac{1}{1,024}\)
which, given input \(2^{n}\cdot 89\), outputs \(2^m\), where \(m\) is the \(n\)th digit of \(\pi\).
Sources[]
- ↑ J. H. Conway, FRACTRAN: A Simple Universal Computing Language for Arithmetic, in: Open Problems in Communication and Computation (T. M. Cover and B. Gopinath, Eds.), Springer-Verlag: New York 1987, pp. 3-27 (Reprinted in [2])
- ↑ The Ultimate Challenge: The 3x+1 Problem. Jeffrey C. Lagarias (Ed.). American Mathematical Society 2010.
See also[]
Bignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion