[Math] A Turing machine which computes $x^y$

automataturing-machines

Question:

Design a Turing machine which takes two integers $x$ and $y$ and outputs $x^y$.

Note 1: The representation of $x$ and $y$ is not mentioned in the question but you can use either the binary or the unary one.

Note 2: I know how to design a Turing machine for $x\cdot y$ and I think it can be helpful in designing the machine which the question wants. But I don't know how. Any idea?

Thanks in advance.

Best Answer

You say you know how to design a Turing machine for $x\cdot y$.

Do you know how to check if a number is $0$, and go to a halting state?

Can you subtract $1$ from a number?

Start off the input with x#y, where # is some separator symbol. Append $1$, giving x#y#1. Now encode the following:

If the second number is $0$, halt (with potential cleanup for output first).
Multiply the third number by the first number.
Subtract $1$ from the second number.
Goto 1.

Related Solutions

[Math] Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

You can move the head right until you find a $b$, than using a 4° symbol $o$ to "cancel" pair of letter a,b until you don't have any $a$, then travel right until you found a $c$ and repeat. This is the general idea (but it'll be my way, I'm not used to work with touring machine and may be quite overcomplicated) and will need a lot of adjustment and you will have to consider a lot of subcase and situation.

[Math] Designing a Turing machine for Binary Multiplication

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).

Best Answer

Related Solutions

[Math] Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

[Math] Designing a Turing machine for Binary Multiplication

Related Question