Entwerfen Sie eine Turing-Maschine, die zwei nicht negative Zahlen eingibt und die Mod-Operation an ihnen ausführt, z. B. mod (3,7) = 3 und mod (7,3) = 1. Geben Sie alle Annahmen und Formate über die Eingabe und Ausgabe des TM eindeutig an.Turing Machine: nimm einen Mod aus zwei Zahlen?
Eingabe besteht aus zwei positiven ganzen Zahlen X und Y, die durch ein Trennzeichen getrennt sind. Ausgabe ist eine einzelne Zahl Z in unary. TM ist einseitiges Einzelband deterministisch.
Bewegen Sie sich zuerst nach rechts, um den Separator zu finden. Springen Sie dann zwischen dem Ende von X und dem Anfang von Y hin und her und markieren Sie die Symbolpaare. Wenn Sie kein X mehr haben, bevor Sie Y verlassen haben, dann X < Y und X mod Y = X; lösche das Trennzeichen und alles danach, ändere dann alle Bandsymbole auf deine unäre Zahl und halte halt an. Wenn Sie vor X kein Y mehr haben, dann ändern Sie die markierten Symbole in X zu gelöscht/Trennzeichen, stellen markierte Symbole von Y auf die unäre Stelle und wiederholen (X> = Y, also X mod Y = (X - Y) mod Y)).
Hier ist, wie Sie Ihre 2 mod 3 verarbeitet wird:
#110111#
#1a0b11#
#aa0bb1#
#aa#####
#11#####
Hier ist, wie 3 mod 2 verarbeitet wird:
#111011#
#11a0b1#
#1aa0bb#
#100011#
#a000b1#
#a######
#1######