I want to draw an state diagram for a Turing machine such as:
If "a" and "b" are the inputs, output in tape will be $a^b$.

I saw many Turing machines that output:

$a+b$ $~~$ ,$~~$ $a-b$ $~~$ , $~~$$a*b$ $~~$ ,$~~$ $a/b$

And also I know how to design a Turing machine for accepting $x^{2^n}$,$x^{3^n}$ and ... But for generating I have no idea...

Question 1:

Is it possible to improve $a*b$ Turing machine inorder to generate $a^b$ ? How ?

Question 2:

Should we add more than one tape to this machine or thats easy to show even with only one tape?


1 Answer 1

  1. It is possible. Practically, $a^b=a*a*a*\dots*a$, hence can be computed using a combination of the multiplication turing machine (to compute the multiplications), and the subtraction TM, in order to count the number of multiplications.

  2. There is a reduction from multiple tapes TM to a single tape TM, so anything possible with multiple tapes is also possible with a single tape (with increased time complexity). To see why, try to think of the "even" spots in a tape as one single tape, and all the "odd" spots as another tape. This allows us to effectively place any number of TM tapes inside one single tape, but if you look carefully into the way its implemented you will see that it will come at the cost of increased time complexity (specifically, its bounded by the space complexity times the time complexity of the multiple tape machine)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.