## FANDOM

10,127 Pages

$$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 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{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$$.

## 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.