Benutzer:Simeon-ohne-Hund/Entwurf

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},\dotsb ,f_{k}.$ Der Name FRACTRAN ist ein Wortspiel und bezieht sich auf die Programmiersprache FORTRAN (FORmula TRANslation = Formelübersetzung). FRACTRAN heißt also soviel 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 $N$ als Startzahl wird nacheinander so lange mit den Brüchen $f$ multipliziert, bis das Podukt $Nf$ wiederum eine ganze Zahl ist. In diesem Fall wird $N$ durch $Nf$ ersetzt und man beginnt mit der neuen Zahl $N$ 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 $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=minA_{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 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

${\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$ 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äßt 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:

${\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_{280}=2^{5},N_{707}=2^{7},N_{2363}=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.

Notiz

Weitere Beispiele zu FRACTRAN-Programmen finden Sie auf der englisch-sprachigen Wikipedia-Seite.

Literatur

• Julian Havil: Verblüfft?!: Mathematische Beweise unglaublicher Ideen, Springer-Verlag, Berlin Heidelberg 2009, S. 155 - 170, ISBN 978-3-642-32318-8
• Dominic Olivastro: Das chinesische Dreieck: Die kniffligsten Rätsel aus 10.000 Jahren, Zweitausendeins, Frankfurt 2006, S. 30 - 38, ISBN 3-86150-764-1

Weblinks

• Online-Rechner für FRACTRAN-Programme