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 $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, von Conway auch als fraction game bezeichnet,^[1] wird folgendermaßen „gespielt“:

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

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

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

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

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

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

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 kurze Programm

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

erzeugt mit der Startzahl $N=72$ die Folge $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 ein FRACTRAN-Programm besser zu verstehen, ist es sinnvoll, die Zahlen der erzeugten Folge in Primfaktoren zu zerlegen:

$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 $N=72=2^{a}\cdot 3^{b}$ als Eingaben in das Programm, also $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 $N=2^{a}\cdot 3^{b}$ in die Zahl $N_{2b}=2^{a+b}$ überführt. Es handelte sich also um ein Additionsprogramm. Das hätte man mit dem FRACTRAN-Programm ${\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

{\frac {1}{6}}

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

Das 2a - Programm

{\frac {9}{2}}

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

Das max (a, b) - Programm

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

Die Startzahl ist $N=2^{a}\cdot 3^{b}.$ Nach max (a, b) Schritten endet die erzeugte Folge mit $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 ${\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 ${\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 max (a, b) - Programm lässt sich sehr einfach zu einem min (a, b) - Programm umschreiben, indem die beiden letzten Zähler von 5 auf 1 geändert werden.

Das Fibonacci - Programm

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

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

Conways PRIMEGAME

Das sicherlich bekannteste FRACTRAN-Programm ist Conways PRIMEGAME^[3]:

{\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 $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: $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: $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 im Verlauf des Programms sehr groß werden kann, ist es sinnvoll, das obige Programm so zu erweitern, dass nicht mehr die Zahl N, sondern nur noch die Exponenten von N verarbeitet werden.

Einzelnachweise

↑ 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.
↑ Dimitri Hendriks: FRACTRAN, 2011 (PDF; 256 kB)
↑ 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

[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

[1]

[2]

[3]