Question

Give an informal description (in plain English) of a Turing machine with three tapes that receives as input two non-negative integers x and y, and returns as output the integer xy. Integers are represented as binary strings.

Start of the computation: The first tape contains the binary representation of x and its head is on the rightmost symbol of x. The second tape contains the binary representation of y and its head is on the rightmost symbol of y. The third tape is empty and its head is at an arbitrary location. The Turing machine is in the start state q₀.

End of the computation: The first and second tapes are empty. The third tape contains the binary representation of the product x y and its head is on the rightmost bit of x y. The Turing machine is in the final state q₁.

Answer 1

Task is very simple. Product of two numbers x and y can be considered equivalent to performing addition of number x total y times. So the Turing machine will perform the following task:-

1. Reduce the content of tape 2 by 1, which is equivalent to reducing y by 1 if tape 2 content is not 0. If tape 2 contains 0 then go to step 4.

2. Perform the addition of content of tape 3 with the content of tape 1.

3. Repeat steps 1 and 2 till tape 2 is not zero.

4. Make tape 1 and tape 2 empty and move the tape 3 head to the rightmost position of xy with state q₁ and halt.

Thus above Turing machine will load xy in tape 3 at the end as per the specification.