Pr.imzahlentester in J--Flap als Tµring Maschine

Ansätze:

J--Flap - vielleicht JFLAP?: http://www.jflap.org/
Turingmaschine: http://de.wikipedia.org/wiki/Turingmaschine
Primzahlen: http://de.wikipedia.org/wiki/Primzahlen
Google: http://google.com

Du wirst vermutlich zuerst schauen müssen, was eine Turingmaschine überhaupt ist, dann dir eine Turing-Maschine überlegen die Primzahlen testet.

Der einfachste (algorithmische) Ansatz ist wohl, einfach zu probieren ob man die getestete Zahl "n" durch irgendeine Zahl "i" von 2 bis n/2 durchdivideren kann (= so oft i aus n subtrahieren bis das Ergebnis <i ist, wenn es 0 ist dann lässt sich n durch i durchdividieren). Das, was ich gerade pseudocodeartig beschrieben habe, muss dann in die "Programmiersprache" der Turingmaschine übersetzt werden (Details siehe z.B. Wikipedia). Das ist vermutlich das Schwierigste an der ganzen Geschichte. Dann gilt es nur noch, die Turing-Maschine in diesem JFLAP-Framework zu implementieren (in JFLAP einlesen, ein paar Tutorials machen, Dokumentation verfolgen... - ich kenne es selber nicht).

Zitat von -0mea-

Pr.imzahlentester
[...]
J--Flap
[...]
Tµring Maschine

Da hat wohl wer Angst, dass der Lehrer bei einer Google-Suche nach "Primzahlentester", "JFLAP" und "Turingmaschine" diesen Thread findet.

Einfach einen simplent Fermat Test[1] implementieren.
Wegen Carmichael-Zahlen[2] aufpassen und daher evtl. gleich einen Miller-Rabin Test[3] implementieren.

lg

[1] http://en.wikipedia.org/wiki/Fermat_test
[2] http://en.wikipedia.org/wiki/Carmichael_number
[3] http://en.wikipedia.org/wiki/Miller-Rabin_primality_testhttp://en.wikipedia.org/wiki/Carmichael_number

Zitat von mdk

Da hat wohl wer Angst, dass der Lehrer bei einer Google-Suche nach "Primzahlentester", "JFLAP" und "Turingmaschine" diesen Thread findet.

und du warst gleich so nett und hast den thread getagged mit diesen begriffen? :multishiner:

http://www.jflap.org/tutorial/

gibt unter anderem eins für eine turing maschine

Eine Turingmaschine in JFLAP, die Primzahlen testet, ist leicht programmiert.