Chapter 13.5, Problem 26E

Construct a Turning machine that computes the function $f\left(n_1,n_2\right)=n_1+n_2+1$ for all nonnegative integers n₁and n₂.

Suppose that T₁, and T₂are Turing machines with disjoint sets of states S₁, and S₂and with transition functions f₁and f₂, respectively. We can define the Turning machine T₁T₂, the composite of T₁, and T₂, as follows. The set of states of T₁, T₂is $S_1\cup S_2$ . T₁T₂begins in the start state of T₁. It first executes the transitions of T₁, using f₁up to, but not including, the step at which T₁, would halt. Then, for all moves for which T₁halts, it executes the same transitions of T₁, except that it moves to the start state of T₂? From this point on, the moves of T₁T₂are the same as the moves of T₂.