Multiplication et machine de turing module

Question

J'ai besoin d'aide pour concevoir une machine Turing qui calculera ce qui suit f(x,y) = x*y mod 4. comment aborder ce problème dans la base binaire où $x$ et $y$ Vous avez deux bits?

Answer 1

Cela pourrait probablement être légèrement optimisé, mais il fait l'affaire:

Hypothèse - l'entrée se compose (uniquement) de deux nombres binaires (avec un leader 0, donc 01 au lieu de 1 et 00 au lieu de 0), séparé par un symbole vide (_). Le résultat est un nombre binaire avec le leading, représentant x * y mod 4.

Table de transition (état 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

Description de l'état approximatif:

• 0 Déplacement à droite du premier numéro (en allant à droite)
• 1 Déplacer à droite du deuxième nombre (et terminer - Ajouter x) -
• 2 Écrivez le premier résultat zéro
• 3 Écrivez le deuxième résultat zéro
• 4 Déplacez-vous à x (allant à gauche)
• 5 Déplacez-vous à droite du premier numéro (à gauche)
• 6 Numéro de droite de diminution d'un
• 7 décrémentée - maintenant le numéro de copie - Déplacez-vous au chiffre de gauche du numéro de droite
• 8 Lire le chiffre de gauche du numéro de droite
• 9 Lire le bon chiffre du bon numéro
• 10 Le chiffre droit du bon nombre était de 1 - Déplacer à droite du résultat à l'incrément
• 11 Résultat d'incrément
• 12 Déplacez-vous à x
• 13 Déplacer pour lire le chiffre à droite du bon numéro
• 14 Déplacer à gauche numérique du résultat à l'incrément
• 15 Numéro de droite incrément (Remarque - Puisque c'est MOD 4, nous ne faisons que retourner)
• 16 Lorsqu'il a essayé de diminuer le numéro de gauche - le chiffre droit était 0 - Vérifiez si 00?
• 17 Nous avons diminué le nombre gauche de 2, désormais augmenter au total -1
• 18 Lorsque le chiffre à gauche du résultat incrémente était de 0 - report
• 19 Nettoyage