www.wikidata.de-de.nina.az

FRACTRAN ist eine Turing vollständige esoterische Programmiersprache des englischen Mathematikers John H Conway Ein Prog

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

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

  1. Eine positive ganze Zahl als Startzahl wird nacheinander mit den Brüchen multipliziert, solange bis das Produkt wiederum eine ganze Zahl ist. In diesem Fall wird durch 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, wobei das FRACTRAN-Programm, die erzeugte Folge und die Menge aller Indizes ist, für die das Produkt zu einer ganzen Zahl wird:

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 Bearbeiten

Das kurze Programm

erzeugt mit der Startzahl die Folge Aber was hat das mit einem Programm zu tun, warum ist die Startzahl 72 und warum endet das Programm?

Das erste Beispiel genauer betrachtet Bearbeiten

Um ein FRACTRAN-Programm besser zu verstehen, ist es sinnvoll, die Zahlen der erzeugten Folge in Primfaktoren zu zerlegen:

Wir betrachten jetzt in erster Linie die Exponenten der Startzahl als Eingaben in das Programm, also 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 in die Zahl überführt. Es handelte sich also um ein Additionsprogramm. Das hätte man mit dem FRACTRAN-Programm allerdings auch kürzer haben können, zumal es auch nur halb so viele Schritte bis zur Lösung benötigt.

Weitere Beispiele Bearbeiten

Das (a - b) - Programm Bearbeiten

Die Startzahl ist wiederum wobei a größer oder gleich b sein sollte. Die erzeugte Folge endet mit

Das 2a - Programm Bearbeiten

Die Startzahl ist Die erzeugte Folge endet mit

Das max (a, b) - Programm Bearbeiten

Die Startzahl ist Nach max (a, b) Schritten endet die erzeugte Folge mit Das Programm arbeitet folgendermaßen: Zunächst werden durch Multiplikation mit dem ersten Bruch 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 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 Bearbeiten

Das folgende FRACTRAN-Programm berechnet die n-te Fibonacci-Zahl :

Die Startzahl ist Die erzeugte Folge endet mit der Zahl . So führt z. B. die Startzahl zum Ergebnis , wobei 13 die 7. Fibonaccizahl ist.

Conways PRIMEGAME Bearbeiten

Das sicherlich bekannteste FRACTRAN-Programm ist Conways PRIMEGAME:

Mit der Startzahl 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:

Ein Java-Programm Bearbeiten

Das folgende Java-Programm multipliziert 5 mit 2: 

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 Bearbeiten

  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 Bearbeiten

  • 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 Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
FRACTRAN ist eine Turing vollstandige esoterische Programmiersprache des englischen Mathematikers John H Conway Ein FRACTRAN Programm besteht aus einer endlichen Folge positiver Bruche f 1 f 2 f k displaystyle f 1 f 2 dotsc f k Der Name FRACTRAN ist ein Wortspiel und bezieht sich auf die Programmiersprache FORTRAN FORmula TRANslation Formelubersetzung und das englische Wort fur Bruch fraction FRACTRAN heisst also so viel wie FRACtion TRANslation Bruchubersetzung Inhaltsverzeichnis 1 FRACTRAN ausfuhren 2 Ein erstes Beispiel 2 1 Das erste Beispiel genauer betrachtet 3 Weitere Beispiele 3 1 Das a b Programm 3 2 Das 2a Programm 3 3 Das max a b Programm 3 4 Das Fibonacci Programm 3 5 Conways PRIMEGAME 4 Ein Java Programm 5 Einzelnachweise 6 Literatur 7 WeblinksFRACTRAN ausfuhren BearbeitenFRACTRAN von Conway auch als fraction game bezeichnet 1 wird folgendermassen gespielt Eine positive ganze Zahl N displaystyle N nbsp als Startzahl wird nacheinander mit den Bruchen f displaystyle f nbsp multipliziert solange bis das Produkt N f displaystyle Nf nbsp wiederum eine ganze Zahl ist In diesem Fall wird N displaystyle N nbsp durch N f displaystyle Nf nbsp ersetzt und man beginnt mit der neuen Zahl wieder von vorne Wenn keiner der Bruche eine ganze Zahl erzeugt endet das Programm bzw Spiel FRACTRAN lasst sich auch formaler beschreiben 2 wobei P displaystyle P nbsp das FRACTRAN Programm N n displaystyle N n nbsp die erzeugte Folge und A n displaystyle A n nbsp die Menge aller Indizes ist fur die das Produkt N n f i displaystyle N n f i nbsp zu einer ganzen Zahl wird P f 1 f 2 f 3 f k f i Q displaystyle P f 1 f 2 f 3 dotsc f k qquad f i in mathbb Q nbsp N n N 0 N 1 N 2 N 3 displaystyle N n N 0 N 1 N 2 N 3 dotsc nbsp A n i 1 i k N n f i N displaystyle A n i 1 leq i leq k N n f i in mathbb N nbsp N 0 N N N displaystyle N 0 N qquad N in mathbb N nbsp N n 1 N n f i wenn i min A n undefiniert wenn A n displaystyle N n 1 begin cases N n f i amp text wenn i min A n text undefiniert amp text wenn A n emptyset end cases nbsp FRACTRAN erzeugt eine endliche oder auch unendliche Folge von naturlichen Zahlen Wenn der letzte Bruch im FRACTRAN Programm als Nenner eine 1 hat ist die Folge der naturlichen Zahlen auf jeden Fall unendlich Wenn ein fruherer Bruch im FRACTRAN Programm als Nenner eine 1 hat werden die nachfolgenden Bruche beim Multiplizieren nie erreicht und sind somit unnotig fur das Programm Allerdings konnen auch FRACTRAN Programme in denen keiner der Nenner eine 1 ist bei bestimmten Eingaben eventuell endlos laufen Ein erstes Beispiel BearbeitenDas kurze Programm 5 3 2 5 displaystyle frac 5 3 frac 2 5 nbsp erzeugt mit der Startzahl N 72 displaystyle N 72 nbsp die Folge 72 120 200 80 32 displaystyle 72 120 200 80 32 nbsp Aber was hat das mit einem Programm zu tun warum ist die Startzahl 72 und warum endet das Programm Das erste Beispiel genauer betrachtet Bearbeiten Um ein FRACTRAN Programm besser zu verstehen ist es sinnvoll die Zahlen der erzeugten Folge in Primfaktoren zu zerlegen 2 3 3 2 2 3 3 1 5 1 2 3 3 0 5 2 2 4 3 0 5 1 2 5 3 0 5 0 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 nbsp Wir betrachten jetzt in erster Linie die Exponenten der Startzahl N 72 2 a 3 b displaystyle N 72 2 a cdot 3 b nbsp als Eingaben in das Programm also a 3 b 2 displaystyle a 3 b 2 nbsp Wenn wir uns nun die Exponenten der erzeugten Folge anschauen dann sehen wir dass zunachst durch zweimalige Multiplikation mit dem ersten Bruch der Exponent von 3 jeweils um 1 verringert und der Exponent von 5 der ursprunglich 0 war um 1 vergrossert wird bis der Exponent von 3 den Wert 0 erreicht hat Da die nachsten beiden Zahlen der Folgen namlich 200 und 80 nicht durch 3 aber durch 5 geteilt werden konnen kommt nun der zweite Bruch zweimal zum Tragen der Exponent von 2 wird jeweils um 1 vergrossert 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 fuhrt keiner der beiden Bruche bei der Multiplikation zu einer ganzen Zahl das Programm endet und der Exponent von 2 ist die Summe der ursprunglichen Exponenten von 2 und 3 Allgemein wird durch das obige FRACTRAN Programm die Startzahl N 2 a 3 b displaystyle N 2 a cdot 3 b nbsp in die Zahl N 2 b 2 a b displaystyle N 2b 2 a b nbsp uberfuhrt Es handelte sich also um ein Additionsprogramm Das hatte man mit dem FRACTRAN Programm 2 3 displaystyle frac 2 3 nbsp allerdings auch kurzer haben konnen zumal es auch nur halb so viele Schritte bis zur Losung benotigt Weitere Beispiele BearbeitenDas a b Programm Bearbeiten 1 6 displaystyle frac 1 6 nbsp Die Startzahl ist wiederum N 2 a 3 b displaystyle N 2 a cdot 3 b nbsp wobei a grosser oder gleich b sein sollte Die erzeugte Folge endet mit N b 2 a b 3 0 displaystyle N b 2 a b cdot 3 0 nbsp Das 2a Programm Bearbeiten 9 2 displaystyle frac 9 2 nbsp Die Startzahl ist N 2 a displaystyle N 2 a nbsp Die erzeugte Folge endet mit N a 2 0 3 2 a displaystyle N a 2 0 cdot 3 2a nbsp Das max a b Programm Bearbeiten 5 6 5 2 5 3 displaystyle frac 5 6 frac 5 2 frac 5 3 nbsp Die Startzahl ist N 2 a 3 b displaystyle N 2 a cdot 3 b nbsp Nach max a b Schritten endet die erzeugte Folge mit N m a x a b 2 0 3 0 5 m a x a b displaystyle N max a b 2 0 cdot 3 0 cdot 5 max a b nbsp Das Programm arbeitet folgendermassen Zunachst werden durch Multiplikation mit dem ersten Bruch 5 2 3 displaystyle frac 5 2 cdot 3 nbsp die Werte von a und b gleichzeitig jeweils um 1 verringert wahrend c das am Anfang 0 war um 1 vergrossert wird bis a oder b gleich 0 ist Mit den beiden Bruchen 5 2 5 3 displaystyle frac 5 2 frac 5 3 nbsp wird nun auch der Wert von a oder b der noch nicht 0 war schrittweise auf 0 gebracht wahrend c weiterhin um 1 vergrossert wird Das max a b Programm lasst sich sehr einfach zu einem min a b Programm umschreiben indem die beiden letzten Zahler von 5 auf 1 geandert werden Das Fibonacci Programm Bearbeiten Das folgende FRACTRAN Programm berechnet die n te Fibonacci Zahl f n displaystyle f n nbsp 91 33 11 13 1 11 399 34 17 19 1 17 2 7 187 5 1 3 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 nbsp Die Startzahl ist N 2 f 1 3 f 0 5 n 1 displaystyle N 2 f 1 cdot 3 f 0 cdot 5 n 1 nbsp Die erzeugte Folge endet mit der Zahl 2 f n displaystyle 2 f n nbsp So fuhrt z B die Startzahl 31250 2 1 3 0 5 6 displaystyle 31250 2 1 cdot 3 0 cdot 5 6 nbsp zum Ergebnis 8192 2 13 displaystyle 8192 2 13 nbsp wobei 13 die 7 Fibonaccizahl ist Conways PRIMEGAME Bearbeiten Das sicherlich bekannteste FRACTRAN Programm ist Conways PRIMEGAME 3 17 91 78 85 19 51 23 38 29 33 77 29 95 23 77 19 1 17 11 13 13 11 15 2 1 7 55 1 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 nbsp Mit der Startzahl N 2 displaystyle N 2 nbsp wird eine Folge erzeugt die in der richtigen Reihenfolge genau die Zweierpotenzen enthalt 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 displaystyle N 19 2 2 N 69 2 3 N 281 2 5 N 710 2 7 N 2375 2 11 nbsp Ein Java Programm BearbeitenDas folgende Java Programm multipliziert 5 mit 2 N 288 2 5 3 2 N 42 9765625 5 10 displaystyle N 288 2 5 cdot 3 2 N 42 9765625 5 10 nbsp 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 amp amp 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 gross 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 Bearbeiten 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 A007542Literatur BearbeitenJohn 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 Verblufft 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 Ratsel aus 10 000 Jahren Zweitausendeins Frankfurt 2006 ISBN 3 86150 764 1 S 30 38 Weblinks BearbeitenOnline Rechner fur FRACTRAN Programme Die einfachste Programmiersprache der Welt FRACTRAN auf YouTube von Edmund Weitz Abgerufen von https de wikipedia org w index php title FRACTRAN amp oldid 220631763