represented by w(x) ∈{1} + , such that
|w(x)| = x.
We must also decide how x and y are placed on the tape initially and
howtheir sum is to appear at the end of the computation. We will assume that
w(x) and w(y) are on the tape in unary notation, separated by a single 0, with the
read-write head on the leftmost symbol of w(x). After the computation, w (x+ y)
will be on the tape followed by a single 0, and the read-write head will be
positioned at the left end of the result. We therefore want to design a Turing
machine for performing the computation
where q f is a final state. Constructing a program for this is relatively simple. All
we need to do is to move the separating 0 to the right end of w (y), so that the
addition amounts to nothing more than the coalescing of the two strings. To
achieve this, we construct M =(Q,Σ,Γ,δ,q 0 , ,F), with Q = {q 0 ,q 1 ,q 2 ,q 3 ,q 4 },F=
{q 4 }, and
δ (q 0 ,1)=(q 0 ,1,R),
δ (q 0 ,0)=(q 0 ,1,R),
δ (q 1 ,1)=(q 1 ,1,R),
δ (q 1 , )=(q 2 , ,L),
δ (q 2 ,1)=(q 3 ,0,L),
δ (q 3 ,1)=(q 3 ,1,L),
δ (q 3 , )=(q 4 , ,R),
Note that in moving the 0 right we temporarily create an extra 1, a fact that is
remembered by putting the machine into state q 1 . The transition δ (q 2 ,1) =
(q 3 ,0,R) is needed to remove this at the end of the computation. This can be seen
from the sequence of instantaneous descriptions for adding 111 to 11:
|w(x)| = x.
We must also decide how x and y are placed on the tape initially and
howtheir sum is to appear at the end of the computation. We will assume that
w(x) and w(y) are on the tape in unary notation, separated by a single 0, with the
read-write head on the leftmost symbol of w(x). After the computation, w (x+ y)
will be on the tape followed by a single 0, and the read-write head will be
positioned at the left end of the result. We therefore want to design a Turing
machine for performing the computation
where q f is a final state. Constructing a program for this is relatively simple. All
we need to do is to move the separating 0 to the right end of w (y), so that the
addition amounts to nothing more than the coalescing of the two strings. To
achieve this, we construct M =(Q,Σ,Γ,δ,q 0 , ,F), with Q = {q 0 ,q 1 ,q 2 ,q 3 ,q 4 },F=
{q 4 }, and
δ (q 0 ,1)=(q 0 ,1,R),
δ (q 0 ,0)=(q 0 ,1,R),
δ (q 1 ,1)=(q 1 ,1,R),
δ (q 1 , )=(q 2 , ,L),
δ (q 2 ,1)=(q 3 ,0,L),
δ (q 3 ,1)=(q 3 ,1,L),
δ (q 3 , )=(q 4 , ,R),
Note that in moving the 0 right we temporarily create an extra 1, a fact that is
remembered by putting the machine into state q 1 . The transition δ (q 2 ,1) =
(q 3 ,0,R) is needed to remove this at the end of the computation. This can be seen
from the sequence of instantaneous descriptions for adding 111 to 11: