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 <math>f_1, f_2,\dotsc, f_k.</math> Der Name FRACTRAN ist ein Wortspiel und bezieht sich auf die Programmiersprache FORTRAN (FORmula TRANslation = Formelübersetzung). FRACTRAN heißt also so viel wie FRACtion TRANslation = Bruchübersetzung.

FRACTRAN ausführen

FRACTRAN, von Conway auch als fraction game bezeichnet, wird folgendermaßen „gespielt“:

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

FRACTRAN läßt sich auch formaler beschreiben, wobei <math>P</math> das FRACTRAN-Programm, <math>\{N_n\}</math> die erzeugte Folge und <math>A_n</math> die Menge aller Indizes ist, für die das Produkt <math>N_nf_i</math> zu einer ganzen Zahl wird:

<math>P = f_1, f_2, f_3, \dotsc, f_k\qquad(f_i \in \mathbb{Q})</math>

<math>\{N_n\} = N_0, N_1, N_2, N_3, \dotsc</math>

<math>A_n = \{i\ |\ 1 \le i \le k,\ N_nf_i \in \mathbb{N}\}</math>

<math>N_0 = N\qquad(N \in \mathbb{N})</math>

<math>

N_{n+1}=\begin{cases}

 N_nf_i,  & \text{wenn }i = \min A_n\\
 \text{undefiniert}, & \text{wenn }A_n = \empty

\end{cases} </math>

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 nachfolgen 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

<math>\frac{5}{3}, \frac{2}{5}</math>

erzeugt mit der Startzahl <math>N = 72</math> die Folge <math>72, 120, 200, 80, 32.</math> 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:

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

<math>\frac{1}{6}</math>

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

Das 2a - Programm

<math>\frac{9}{2}</math>

Die Startzahl ist <math>N = 2^a.</math> Die erzeugte Folge endet mit <math>N_a = 2^0 \cdot 3^{2a}.</math>

Das max (a, b) - Programm

<math>\frac{5}{6}, \frac{5}{2}, \frac{5}{3}</math>

Die Startzahl ist <math>N = 2^a \cdot 3^b.</math> Nach max (a, b) Schritten endet die erzeugte Folge mit <math>N_{max(a,b)} = 2^0 \cdot 3^0 \cdot 5^{max(a,b)}.</math> Das Programm arbeitet folgendermaßen: Zunächst werden durch Multiplikation mit dem ersten Bruch <math>\frac{5}{2 \cdot 3}</math> 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 <math>\frac{5}{2}, \frac{5}{3}</math> 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 <math>f_n</math>:

<math>\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}</math>

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

Conways PRIMEGAME

Das sicherlich bekannteste FRACTRAN-Programm ist Conways PRIMEGAME:

<math>\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}</math>

Mit der Startzahl <math>N = 2</math> 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: <math>N_{19} = 2^2, N_{69} = 2^3, N_{281} = 2^5, N_{710} = 2^7, N_{2375} = 2^{11}.</math>

Ein Java-Programm

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

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.

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