FRACTRAN

FRACTRAN ist eine Turing-vollständige esoterische Programmiersprache des englischen Mathematikers John H. Conway. Ein FRACTRAN-Programm besteht aus einer endlichen Folge positiver Brüche ${\displaystyle f_{1},f_{2},\dotsc ,f_{k}.}$ Der Name FRACTRAN ist ein Wortspiel und bezieht sich auf die Programmiersprache FORTRAN (FORmula TRANslation = Formelübersetzung) und das englische Wort für Bruch (fraction). FRACTRAN heißt also so viel wie FRACtion TRANslation = Bruchübersetzung.

FRACTRAN ausführen

FRACTRAN, v​on Conway a​uch als fraction game bezeichnet,[1] w​ird folgendermaßen „gespielt“:

1. Eine positive ganze Zahl ${\displaystyle N}$ als Startzahl wird nacheinander mit den Brüchen ${\displaystyle f}$ multipliziert, solange bis das Produkt ${\displaystyle Nf}$ wiederum eine ganze Zahl ist. In diesem Fall wird ${\displaystyle N}$ durch ${\displaystyle Nf}$ ersetzt und man beginnt mit der neuen Zahl wieder von vorne.
2. Wenn keiner der Brüche eine ganze Zahl erzeugt, endet das Programm bzw. Spiel.

FRACTRAN lässt sich auch formaler beschreiben,[2] wobei ${\displaystyle P}$ das FRACTRAN-Programm, ${\displaystyle \{N_{n}\}}$ die erzeugte Folge und ${\displaystyle A_{n}}$ die Menge aller Indizes ist, für die das Produkt ${\displaystyle N_{n}f_{i}}$ zu einer ganzen Zahl wird:

${\displaystyle P=f_{1},f_{2},f_{3},\dotsc ,f_{k}\qquad (f_{i}\in \mathbb {Q} ^{+})}$

${\displaystyle \{N_{n}\}=N_{0},N_{1},N_{2},N_{3},\dotsc }$

${\displaystyle A_{n}=\{i\ |\ 1\leq i\leq k,\ N_{n}f_{i}\in \mathbb {N} \}}$

${\displaystyle N_{0}=N\qquad (N\in \mathbb {N} )}$

${\displaystyle N_{n+1}={\begin{cases}N_{n}f_{i},&{\text{wenn }}i=\min A_{n}\\{\text{undefiniert}},&{\text{wenn }}A_{n}=\emptyset \end{cases}}}$

FRACTRAN erzeugt eine endliche oder auch unendliche Folge von natürlichen Zahlen. Wenn der letzte Bruch im FRACTRAN-Programm als Nenner eine 1 hat, ist die Folge der natürlichen Zahlen auf jeden Fall unendlich. Wenn ein früherer Bruch im FRACTRAN-Programm als Nenner eine 1 hat, werden die nachfolgenden Brüche beim Multiplizieren nie erreicht und sind somit unnötig für das Programm. Allerdings können auch FRACTRAN-Programme, in denen keiner der Nenner eine 1 ist, bei bestimmten Eingaben eventuell endlos laufen.

Ein erstes Beispiel

Das k​urze Programm

${\displaystyle {\frac {5}{3}},{\frac {2}{5}}}$

erzeugt mit der Startzahl ${\displaystyle N=72}$ die Folge ${\displaystyle 72,120,200,80,32.}$ Aber was hat das mit einem Programm zu tun, warum ist die Startzahl 72 und warum endet das Programm?

Das erste Beispiel genauer betrachtet

Um e​in FRACTRAN-Programm besser z​u verstehen, i​st es sinnvoll, d​ie Zahlen d​er erzeugten Folge i​n Primfaktoren z​u zerlegen:

${\displaystyle 2^{3}\cdot 3^{2},\ 2^{3}\cdot 3^{1}\cdot 5^{1},\ 2^{3}\cdot 3^{0}\cdot 5^{2},\ 2^{4}\cdot 3^{0}\cdot 5^{1},\ 2^{5}\cdot 3^{0}\cdot 5^{0}.}$ Wir betrachten jetzt in erster Linie die Exponenten der Startzahl ${\displaystyle N=72=2^{a}\cdot 3^{b}}$ als Eingaben in das Programm, also ${\displaystyle a=3,b=2.}$ Wenn wir uns nun die Exponenten der erzeugten Folge anschauen, dann sehen wir, dass zunächst durch zweimalige Multiplikation mit dem ersten Bruch der Exponent von 3 jeweils um 1 verringert und der Exponent von 5, der ursprünglich 0 war, um 1 vergrößert wird, bis der Exponent von 3 den Wert 0 erreicht hat. Da die nächsten beiden Zahlen der Folgen, nämlich 200 und 80, nicht durch 3, aber durch 5 geteilt werden können, kommt nun der zweite Bruch zweimal zum Tragen: der Exponent von 2 wird jeweils um 1 vergrößert und der Exponent von 5 um 1 verringert, bis auch er den Wert 0 erreicht hat. Da nun die Exponenten von 3 und 5 beide den Wert 0 haben, führt keiner der beiden Brüche bei der Multiplikation zu einer ganzen Zahl, das Programm endet und der Exponent von 2 ist die Summe der ursprünglichen Exponenten von 2 und 3.

Allgemein wird durch das obige FRACTRAN-Programm die Startzahl ${\displaystyle N=2^{a}\cdot 3^{b}}$ in die Zahl ${\displaystyle N_{2b}=2^{a+b}}$ überführt. Es handelte sich also um ein Additionsprogramm. Das hätte man mit dem FRACTRAN-Programm ${\displaystyle {\frac {2}{3}}}$ allerdings auch kürzer haben können, zumal es auch nur halb so viele Schritte bis zur Lösung benötigt.

Weitere Beispiele

Das (a - b) - Programm

${\displaystyle {\frac {1}{6}}}$

Die Startzahl ist wiederum ${\displaystyle N=2^{a}\cdot 3^{b},}$ wobei a größer oder gleich b sein sollte. Die erzeugte Folge endet mit ${\displaystyle N_{b}=2^{a-b}\cdot 3^{0}.}$

Das 2a - Programm

${\displaystyle {\frac {9}{2}}}$

Die Startzahl ist ${\displaystyle N=2^{a}.}$ Die erzeugte Folge endet mit ${\displaystyle N_{a}=2^{0}\cdot 3^{2a}.}$

Das max (a, b) - Programm

${\displaystyle {\frac {5}{6}},{\frac {5}{2}},{\frac {5}{3}}}$

Die Startzahl ist ${\displaystyle N=2^{a}\cdot 3^{b}.}$ Nach max (a, b) Schritten endet die erzeugte Folge mit ${\displaystyle N_{max(a,b)}=2^{0}\cdot 3^{0}\cdot 5^{max(a,b)}.}$ Das Programm arbeitet folgendermaßen: Zunächst werden durch Multiplikation mit dem ersten Bruch ${\displaystyle {\frac {5}{2\cdot 3}}}$ die Werte von a und b gleichzeitig jeweils um 1 verringert, während c, das am Anfang 0 war, um 1 vergrößert wird, bis a oder b gleich 0 ist. Mit den beiden Brüchen ${\displaystyle {\frac {5}{2}},{\frac {5}{3}}}$ wird nun auch der Wert von a oder b, der noch nicht 0 war, schrittweise auf 0 gebracht, während c weiterhin um 1 vergrößert wird.

Das m​ax (a, b) - Programm lässt s​ich sehr einfach z​u einem m​in (a, b) - Programm umschreiben, i​ndem die beiden letzten Zähler v​on 5 a​uf 1 geändert werden.

Das Fibonacci - Programm

Das folgende FRACTRAN-Programm berechnet die n-te Fibonacci-Zahl ${\displaystyle f_{n}}$:

${\displaystyle {\frac {91}{33}},{\frac {11}{13}},{\frac {1}{11}},{\frac {399}{34}},{\frac {17}{19}},{\frac {1}{17}},{\frac {2}{7}},{\frac {187}{5}},{\frac {1}{3}}}$

Die Startzahl ist ${\displaystyle N=2^{f_{1}}\cdot 3^{f_{0}}\cdot 5^{n-1}.}$ Die erzeugte Folge endet mit der Zahl ${\displaystyle 2^{f_{n}}}$. So führt z. B. die Startzahl ${\displaystyle 31250=2^{1}\cdot 3^{0}\cdot 5^{6}}$ zum Ergebnis ${\displaystyle 8192=2^{13}}$, wobei 13 die 7. Fibonaccizahl ist.

Conways PRIMEGAME

Das sicherlich bekannteste FRACTRAN-Programm i​st Conways PRIMEGAME[3]:

${\displaystyle {\frac {17}{91}},{\frac {78}{85}},{\frac {19}{51}},{\frac {23}{38}},{\frac {29}{33}},{\frac {77}{29}},{\frac {95}{23}},{\frac {77}{19}},{\frac {1}{17}},{\frac {11}{13}},{\frac {13}{11}},{\frac {15}{2}},{\frac {1}{7}},{\frac {55}{1}}}$

Mit der Startzahl ${\displaystyle N=2}$ wird eine Folge erzeugt, die in der richtigen Reihenfolge genau die Zweierpotenzen enthält, deren Exponent eine Primzahl ist. Mit anderen Worten, PRIMEGAME generiert alle Primzahlen, allerdings sehr langsam: ${\displaystyle N_{19}=2^{2},N_{69}=2^{3},N_{281}=2^{5},N_{710}=2^{7},N_{2375}=2^{11}.}$

Ein Java-Programm

Das folgende Java-Programm multipliziert 5 mit 2: ${\displaystyle N=288=2^{5}\cdot 3^{2},N_{42}=9765625=5^{10}.}$

public class Fractran {
    public static void main(String[] args) {
        long N = 288;
        long[] zaehler = {455, 11, 1, 3, 11, 1};
        long[] nenner  = {33, 13, 11, 7, 2, 3};
        int i = 0, j;
        boolean halt = false;
        System.out.println(i + ": " + N);
        while (!halt) {
            j = 0;
            while (!halt && ((N*zaehler[j])%nenner[j] != 0)) {
                j++;
                if (j == zaehler.length) halt = true;
            }
            i++;
            if (!halt) {
                N = (N*zaehler[j])/nenner[j];
                System.out.println(i + ": " + N);
            }
        }
    }
}

Da N i​m Verlauf d​es Programms s​ehr groß werden kann, i​st es sinnvoll, d​as obige Programm s​o zu erweitern, d​ass nicht m​ehr die Zahl N, sondern n​ur noch d​ie Exponenten v​on N verarbeitet werden.

Einzelnachweise

1. J. H. Conway: FRACTRAN: A Simple Universal Programming Language for Arithmetic. In: T. Jeffrey C. Lagarias (Hrsg.):The Ultimate Challenge: The 3x+1 Problem. American Mathematical Soc., 2010, ISBN 978-0-8218-4940-8, S. 249–264.
2. Dimitri Hendriks: FRACTRAN, 2011 (PDF; 256 kB)
3. The On-Line Encyclopedia of Integer Sequences, Folge A007542

Literatur

• John Horton Conway: FRACTRAN: A Simple Universal Programming Language for Arithmetic. In: Thomas M. Cover, B. Gopinath: Open Problems in Communication and Computation. Springer-Verlag, 1987, ISBN 0-387-96621-8, S. 4–26.
• Julian Havil: Verblüfft?!: Mathematische Beweise unglaublicher Ideen. Springer-Verlag, Berlin/ Heidelberg 2009, ISBN 978-3-642-32318-8, S. 155–170.
• Dominic Olivastro: Das chinesische Dreieck: Die kniffligsten Rätsel aus 10.000 Jahren. Zweitausendeins, Frankfurt 2006, ISBN 3-86150-764-1, S. 30–38.

Weblinks

• Online-Rechner für FRACTRAN-Programme
• Die einfachste Programmiersprache der Welt: FRACTRAN auf YouTube von Edmund Weitz