Multiplication and Module Turing Machine

Question

I need help designing a turing machine that will compute the following f(x,y) = x*y mod 4. how to approach this problem in binary base where $x$ and $y$ have two bits?

Answer 1

Assuming that the input consists of 4 symbols, where the left two represent 𝑥 and the other two represent 𝑦, this can be done with 10 states including the start and accept states.

The idea is to read 𝑥 and remove it, resulting in one of four states, each identifying the value of 𝑥. When 𝑥 is 0, then write two zeroes. If 𝑥 is 1, then the answer is 𝑦, so there is nothing to do. When 𝑥 is 2, then wipe out the left digit of 𝑦 and append a 0 at its right. When 𝑥 is 3, then if the rightmost bit of 𝑦 is 1, toggle the other bit.

Here is a transition table for it:

state	read	write	move head	next state
start	0	_	right	num0x
start	1	_	right	num1x
num0x	0	_	right	put00
num0x	1	_	right	accept
num1x	0	_	right	mul
num1x	1	_	right	add
put00	0 or 1	0	right	put00
put00	_		left	accept
mul	0 or 1	_	right	append0
append0	0 or 1		right	append0
append0	_	0	left	accept
add	0 or 1		right	read
read	0		left	accept
read	1		left	toggle
toggle	0	1	right	accept
toggle	1	0	right	accept

Here is a snippet you can run to try different inputs:

createTuring({
    transitions: [
        { state: "start",  read: "0",   write: "_", move: "R", nextState: "num0x"  },
        { state: "start",  read: "1",   write: "_", move: "R", nextState: "num1x"  },
        { state: "num0x",  read: "0",   write: "_", move: "R", nextState: "put00"  },
        { state: "num0x",  read: "1",   write: "_", move: "R", nextState: "accept" },
        { state: "num1x",  read: "0",   write: "_", move: "R", nextState: "mul"    },
        { state: "num1x",  read: "1",   write: "_", move: "R", nextState: "add"    },
        { state: "put00",  read: "01",  write: "0", move: "R", nextState: "put00"  },
        { state: "put00",  read: "_",               move: "L", nextState: "accept" },
        { state: "mul",    read: "01",  write: "_", move: "R", nextState: "append0"},
        { state: "append0",read: "01",              move: "R", nextState: "append0"},
        { state: "append0",read: "_",   write: "0", move: "L", nextState: "accept" },
        { state: "add",    read: "01",              move: "R", nextState: "read"   },
        { state: "read",   read: "0",               move: "L", nextState: "accept" },
        { state: "read",   read: "1",               move: "L", nextState: "toggle" },
        { state: "toggle", read: "0",   write: "1", move: "R", nextState: "accept" },
        { state: "toggle", read: "1",   write: "0", move: "R", nextState: "accept" },
    ],
    initState: "start",
    tape: "0110",
});

<script src="https://trincot.github.io/turing.js"></script>

Answer 2

Could probably be slightly optimised, but it does the trick:

Assumption - input consists (solely) of two binary numbers (with leading 0, so 01 instead of 1 and 00 instead of 0), separated by a blank symbol (_). Result is a binary number with leading, representing x * y mod 4.

Transition table (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

Rough state description:

• 0 move to right of first number (going right)
• 1 move to right of second number (and terminate - add x) -
• 2 write first result zero
• 3 write second result zero
• 4 move to x (going left)
• 5 move to right of first number (going left)
• 6 decrement right number by one
• 7 decremented - now copy number - move to left digit of right number
• 8 read left digit of right number
• 9 read right digit of right number
• 10 right digit of right number was 1 - move to right of result to increment
• 11 increment result
• 12 move to x
• 13 move to read right digit of right number
• 14 move to left digit of result to increment
• 15 increment right number (note - since it's mod 4, we're just flipping)
• 16 when tried to decrement left number - right digit was 0 - check if 00?
• 17 we've decremented left number by 2, now increment to total -1
• 18 when incrementing result left digit was 0 - carryover
• 19 cleanup