Wie schreibe ich ein Turingprogramm ababab?

• Schreibt ein Turing-Programm, das möglichst viele Male "ab" auf das Band schreibt
• Bedingungen:
• Die Turingmaschine muss halten
• Das Eingabealphabet besteht aus {1; 5}
• Das Bandalphabet besteht aus maximal 7 Zeichen
• Zu Beginn ist das Band leer
• Das Programm soll auf dem Turing-Simulator von Mathe-Prisma laufen
• Anforderungen:
• Die Anzahl der Zustände der Maschine sollte so gering wie möglich gehalten werden
• Um eine gute Bewertung zu erhalten, muss die Anzahl der 15en größer als 2^#Zustände sein.

Answer 1

[Destranix]

Wegen der letzten Bedingung muss die Zähllogik irgendwie auf dem Band realisiert werden, sonst wird die Zahl der Durchläufe durch die Zahl der Zustände begrenzt.

Was man versuchen könnte wäre:

1.) Eine Zahl an den Anfang des Bandes schreiben. Diese gibt die Anzahl der 15er an, die ausgegeben werden soll.

2.) Einen Automaten schreiben, der prüft, ob die Zahl 0 ist, diese dnan um 1 verringert, ein 15 auf das Band schreibt und dann wieder zur Zahl zurückläuft.

Die Zahl der zustände ist dabei allerdings nicht gerade gering, deshalb will man vielleicht nach einem anderem Ansatz suchen.

Man könnte beispielsweise jeweils das bereits geschriebene einmal erneut auf das Band kopieren und in den Zuständen mitzählen, wie oft das geschehen ist. Dann könnte man über 2^#Zustände hinaus kommen.

Comments

[clara17487648]

Danke schonmal:), er meinte auch noch der fleißige Bieber könnte uns weiterhelfen…ich weiß aber nicht wie… vielleicht hilft das was

[Destranix]

@clara17487648

Daran dachte ich auch schon. Aber der fleißige Bieber ist kein Problem, das man lösen möchte, deshalb würde ich es eher so machen, wie oben beschrieben.

Dann bekommst du zwar nicht den maximalen Output, der möglich ist mit der Zahl der Zustände, aber dennoch eine recht große Ausgabe.

Zum Fleißigen Bieber siehe:

https://de.wikipedia.org/wiki/Flei%C3%9Figer_Biber

[clara17487648]

@Destranix

ja ich hab es jetzt auch so gemacht mit dem runterzuholen, sehr simpel, aber effektiv

[Destranix]

@clara17487648

Wie genau? Kannst du deine Lösung kurz beschreiben?

Ich hatte gerade auch noch einmal nachgedacht und einige Schwierigkeiten entdeckt und bin mir jetzt nicht mehr so sicher wie effektiv die zweite vorgeschlagene Lösung ist. Das mit dem Zähler würde aber vermutlich funktionieren.