Design a turing machine for addition of binary number

Question

I have been working on the following problem:

{0,1}∗ → N that treats a word of {0,1}∗ as the binary representation of a non-negative integer, with the last symbol being the least-significant. So bin(110) = bin(00110) = 6 and bin() = 0. Design a Turing Machine, that decides the following language:

{x#y#z : x,y,z ∈ {0,1}∗ and bin(x)+bin(y) = bin(z)}

For solving binary addition Full adder seem to be a way to go, I was able to construct a half adder, now things are getting complex and I seem to be stuck, I need a way through which I can send a carry value back to a new half adder or something like that,

I have been using following sample input 1000#0101#1101 Explanation : Numbers are separated using # 8+5=13 (This should be accepted)

Below is the state diagram I have constructed:

[]

[]

Answer 1

I would "shift right" the summands and "remember" the least significant bits, and on the way back for the next round check for "$0+0=0$". This would use the following fifteen states:

• Twelve states SHIFT$t$$s$$m$ for $m\in\{0,1\}$, $s,t\in\{0,1,2\}$ with $s\le t$: "While shifting the $(t+1)$st term where $s$ is the sum of all previous least significant bits and needing to write the previously seen $m$". Here, the previously seen $m$ may be a not-actually-seen $0$ being shifted in from the left. Also, SHIFT$\bf000$ (while standing on the first symbol) is the initial state.

• Two states BACK$v$ for $v\in\{\bot,\top\}$: "Moving back to the leftmost position and so far the truh value of $0+0=0$ seems to be $v$"

• One state DEC: "Decrementing the third term"

Transition rules are as follows:

$\textbf{SHIFT}tsm$:

• $0 \mapsto (m, R, \textbf{SHIFT}ts0)$
• $1 \mapsto (m, R, \textbf{SHIFT}ts1)$
• If $t<2$: $\#\mapsto (\#, R, \textbf{SHIFT}(t+1)(s+m)0)$
• If $t=2$ and $s=m$: $\sqcup\mapsto (\sqcup,L,\textbf{BACK}\top)$
• If $t=2$ and $s=$ and $m=0$: $\sqcup\mapsto (\sqcup,L,\textbf{DEC})$

$\textbf{BACK}v$:

• $0\mapsto (0,L,\textbf{BACK}v)$
• $1\mapsto (1,L,\textbf{BACK}\bot)$
• $\#\mapsto (\#,L,\textbf{BACK}v)$
• if $v=\top$: $\sqcup\mapsto $ HALT with ACCEPT

$\textbf{DEC}$:

• $1\mapsto (0,L,\textbf{BACK}\bot)$
• $0\mapsto (1,L,\textbf{DEC})$

Everything else: HALT with REJECT, of course