1
$\begingroup$

Suppose I wished to devise an algorithm (to be run on a turing machine) which could find the sum of 2 integers (expressed in base2). How many tapes would this require?

My intuition tells me that 4 tapes would be required: 1 for each of the two numbers being added together, 1 to store the 'carry over' value, and 1 to store the output.

Is this correct? Could it be done with fewer tapes?

$\endgroup$
1
  • 2
    $\begingroup$ It can be done with 1 tape. The tapes are infinite, right? $\endgroup$
    – mikeazo
    Nov 1, 2017 at 18:02

1 Answer 1

2
$\begingroup$

Anything that can be computed with any reasonable extension of a Turing machine can be computed with the standard Turing machine that has a single one-way infinite tape.

For example, you can simulate a four-tape machine by interleaving the characters of the tapes so that, e.g., the four tapes

$$\begin{array}{cccc} a_1 & a_2 & a_3 & \cdots\\ b_1 & b_2 & b_3 & \cdots\\ c_1 & c_2 & c_3 & \cdots\\ d_1 & d_2 & d_3 & \cdots \end{array}$$

with the single tape $$a_1\ b_1\ c_1\ d_1\ a_2\ b_2\ c_2\ d_2\ a_3\ b_3\ c_3\ d_3\ \cdots$$

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. How would this machine work though? Would the $c_i$ terms not just be represented by different states of the head? $\endgroup$
    – M Smith
    Nov 2, 2017 at 0:38
  • $\begingroup$ I'm not sure what you mean. The values $c_1, c_2, \dots$ are the characters stored on the third tape. Actually, the situation is slightly more complicated than I stated, since you also need to keep track of where the tape heads are. $\endgroup$ Nov 2, 2017 at 1:15

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.