(computing the sum of natural numbers) Prove that a Turing machine can add natural numbers; that is, outline a (multi-tape) Turing machine that on input a pair of integers (in binary representation)...

(computing the sum of natural numbers) Prove that a Turing

machine can add natural numbers; that is, outline a (multi-tape) Turing machine

that on input a pair of integers (in binary representation) outputs their sum.

Specifically, show that the straightforward addition algorithm can be implemented in linear time by a multi-tape Turing machine.