Wie erstelle ich eine Turingmaschine die sortiert?
Hallo zusammen,
kann mir jemand von euch sagen, wie man eine Turingmaschine erstellt, welche z.B Worte aus dem Alphabet (a, b, c, d) sortiert? Am Ende sollten dann die a‘s vorne stehen und die d‘s als letztes.
Danke für eure Hilfe!
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
programmieren, Informatik
Es gibt unabzählbar unendlich viele Möglichkeiten für eine solche TM und mindestens genausoviele Möglichkeiten, soeine TM zu erdenken.
An sich wäre eine recht simple Möglichkeit, sich einfach ein Haufen Vertauschungsregeln zu erdenken:
ba->ab;
ca->ac;
da->ad;
cb->bc;
db->bd;
dc->cd;
Und die sollen erschöpfend angewendet werden.
Dazu eine TM zu finden ist jetzt trivial.