[Math] Designing a Turing machine for Binary Multiplication

automataturing-machines

I need help designing a turing machine that will compute the following

$$f(x,y) = x\times y$$

How to approach this problem in binary base? This is a assignment so I don't want anyone to solve it for me because I want to do it myself, I just need a little help to design a turing machine for this problem.

I tried to make a logic, which is

  1. First we have to decrement $Y$, until zero.

  2. With each decrement we have to add $X$ to $X$, but I don't know how.

I can't solve any further.

Best Answer

That sounds like a good plan -- except you don't want to add $x$ to $x$; you want to add $x$ to a separate counter that starts at $0$.

Do you already have a machine for addition with the number representation you use (which preserves one of the operands on the tape and increases the other destructively)? Otherwise start by making that.

Alternatively if you're representing the integers in base-2 you could replicate the usual long multiplication algorithm:

Set T=0
While X != 0:
   If the lowest bit of X is 1:
      Set T=T+Y
   End if
   Remove the lowest bit from X
   Append a 0 bit at the end low of Y
End while
The result is in T

This may not even be more complex to program, and will run faster (though that is typically not a relevant consideration when we talk about Turing machines. It might be a relevant difference here because it is more than a polynomial difference).

Related Question