FANDOM


\(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\)
37485 \(0\rightarrow 0, n+1\rightarrow n\)
2268945 \(n\rightarrow n+1\)
\(2^{2^{b}-2^{a}}\) \(a\rightarrow b\)
\(7\cdot 11^{2^{k}}\) \(n\rightarrow k\)
\(\frac{15}{7}\cdot 1029^{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 Edit

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 Edit

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{3159}{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}{1024}\)

which, given input \(2^{n}\cdot 89\), outputs \(2^m\), where \(m\) is the \(n\)th digit of \(\pi\).

SourcesEdit

  1. 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])
  2. The Ultimate Challenge: The 3x+1 Problem. Jeffrey C. Lagarias (Ed.). American Mathematical Society 2010.

See alsoEdit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.