Multiplikation und Modul -Turing -Maschine

Question

Ich brauche Hilfe beim Entwerfen einer Turing -Maschine, die Folgendes berechnet f(x,y) = x*y mod 4. Wie man diesem Problem in der binären Basis angeht, wo $x$ und $y$ Haben Sie zwei Teile?

Answer 1

Könnte wahrscheinlich leicht optimiert werden, aber es macht den Trick:

Annahme - Eingabe besteht (ausschließlich) von zwei Binärzahlen (mit führender 0, also 01 anstelle von 1 und 00 anstelle von 0), getrennt durch ein leeres Symbol (_). Das Ergebnis ist eine binäre Zahl mit der Führung, die X * y Mod 4 darstellt.

Übergangstabelle (STATE Current_Symbol new_symbol move_direction new_state):

0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ x r 2
2 _ 0 r 3 
3 _ 0 l 4
4 0 0 l 4
4 x x l 5
5 0 0 l 5
5 1 1 l 5
5 x x l 5
5 _ _ l 6
6 1 0 r 7
6 0 0 l 16
7 0 0 r 7
7 1 1 r 7
7 _ _ r 7
7 x x l 8
8 0 0 l 9
8 1 1 r 10
9 0 0 l 5
9 1 1 r 14
10 x x r 10
10 0 0 r 11
10 1 1 r 11
11 0 1 l 12
11 1 0 l 18
12 0 0 l 12
12 1 1 l 12
12 x x l 13
13 0 0 l 9
13 1 1 l 9
14 0 0 r 14
14 1 1 r 14
14 x x r 15
15 0 1 r 5
15 1 0 r 5
16 0 _ r 19
16 1 0 r 17
17 0 1 r 7
18 0 1 l 12
18 1 0 l 12
19 0 _ r 19
19 1 _ r 19
19 _ _ r 19
19 x _ r halt

Beschreibung der rauen Zustand:

• 0 Ziehen Sie nach rechts von der ersten Zahl (rechts) (rechts)
• 1 Bewegen Sie sich nach rechts in der zweiten Zahl (und enden Sie add x) -
• 2 Erstes Ergebnis Null schreiben
• 3 Schreiben Sie zweites Ergebnis Null
• 4 Wechseln Sie nach X (links gehen)
• 5 Gehen Sie nach rechts von der ersten Zahl (links)
• 6 Abnahme der richtigen Zahl um eins
• 7 Dekrementiert - jetzt Kopienzahl - zur linken Ziffer der rechten Zahl wechseln
• 8 Lesen Sie die linke Ziffer der rechten Zahl
• 9 Lesen Sie die rechte Ziffer der rechten Zahl
• 10 Rechte Ziffer der rechten Zahl war 1 - Wechsel rechts vom Ergebnis nach Inkrement
• 11 Inkrement -Ergebnis
• 12 Wechsel zu x
• 13 Bewegen Sie, um die rechte Ziffer der rechten Zahl zu lesen
• 14 Bewegen
• 15 Inkrement -Rechtsnummer (Hinweis - Da es sich um Mod 4 handelt, flippen wir nur)
• 16 Beim Versuch, die linke Zahl zu verringern - rechte Ziffer war 0 - Überprüfen Sie, ob 00?
• 17 Wir haben die linke Zahl um 2 verringert, nun auf insgesamt -1 erhöht
• 18 Beim Inkrementierungsergebnis links die Ziffer 0 - Übertragung
• 19 Aufräumarbeiten