Design a turing machine for addition of binary number 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:
[]
[]
 A: 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
