Máquina de Turing de multiplicação e módulo

Question

Preciso de ajuda para projetar uma máquina de Turing que calcule o seguinte f(x,y) = x*y mod 4. Como abordar esse problema na base binária onde $x$ e $y$ tem dois bits?

Answer 1

Provavelmente poderia ser um pouco otimizado, mas faz o truque:

Suposição - a entrada consiste (apenas) de dois números binários (com a liderança 0, então 01 em vez de 1 e 00 em vez de 0), separados por um símbolo em branco (_). O resultado é um número binário com a liderança, representando X * y Mod 4.

Tabela de transição (estado 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

Descrição do estado aproximado:

• 0 Mova para a direita do primeiro número (indo para a direita)
• 1 mova para a direita do segundo número (e termine - adicione x) -
• 2 Escreva o primeiro resultado zero
• 3 Escreva o segundo resultado zero
• 4 Mova para X (indo para a esquerda)
• 5 Mova para a direita do primeiro número (indo para a esquerda)
• 6 Diminuir o número certo por um
• 7 Diminuir - agora o número da cópia - mova para o dígito esquerdo do número certo
• 8 Leia o dígito esquerdo do número certo
• 9 Leia o dígito certo do número certo
• 10 dígito direito do número certo foi 1 - mova -se para o direito de incremento
• 11 resultado de incremento
• 12 mude para x
• 13 Mova para ler o dígito direito do número certo
• 14 Mova para o dígito esquerdo do resultado para incrementar
• 15 Incremento Número certo (Nota - Como é o mod 4, estamos apenas lançando)
• 16 Quando tentou diminuir o número esquerdo - o dígito direito foi 0 - verifique se 00?
• 17 Decrementamos o número à esquerda em 2, agora incremento para o total -1
• 18 Quando o resultado da esquerda do resultado é 0 - transferência
• 19 Limpeza