a. Let $\mathbf{ADD}\mathbf{=}\mathbf{\left\{}\mathbf{⟨}\mathbf{x}\mathbf{,}\mathbf{y}\mathbf{,}\mathbf{z}\mathbf{⟩}\mathbf{\right|}\mathbf{x}\mathbf{,}\mathbf{y}\mathbf{,}\mathbf{z}\mathbf{>}\mathbf{0}$ are binary integers and $\mathbf{x}\mathbf{+}\mathbf{y}\mathbf{=}\mathbf{z}\mathbf{\}}$. Show
that $\mathbf{ADD}\mathbf{\in }\mathbf{L}$.
b. Let $\mathbf{PAL}\mathbf{\_}\mathbf{ADD}\mathbf{=}\mathbf{\left\{}\mathbf{⟨}\mathbf{x}\mathbf{,}\mathbf{y}\mathbf{⟩}\mathbf{\right|}\mathbf{x}\mathbf{,}\mathbf{y}\mathbf{>}\mathbf{0}$are binary integers where$\mathbf{x}\mathbf{+}\mathbf{y}$ is an integer whose binary representation is a palindrome). (Note that the binary representation of the sum is assumed not to have leading zeros. A palindrome is a string that equals its reverse.) Show that $\mathbf{PAL}\mathbf{\_}\mathbf{ADD}\mathbf{\in }\mathbf{L}$.

The class$\mathrm{L}:\mathrm{L}$ is the class of languages that are decidable in the logarithmic space on the deterministic truing machine. It shows$\mathrm{L}=\mathrm{SPACE}\left(\log \mathrm{n}\right)$ .

The language is,

$\mathrm{ADD}=\left\{⟨\mathrm{x},\mathrm{y},\mathrm{z}⟩|\mathrm{x},\mathrm{y},\mathrm{z}>0\mathrm{are}\mathrm{binary}\mathrm{integers}\mathrm{and}\mathrm{x}+\mathrm{y}=\mathrm{z}\right\}$

The condition is to prove that $\mathrm{ADD}\in \mathrm{L}$.

Let${\mathrm{M}}_1$ be the DTM that decides ADD in the logarithmic space.

The construction of ${\mathrm{M}}_1$is as follows:

${\mathrm{M}}_1="\mathrm{On}\mathrm{input}⟨\mathrm{x},\mathrm{y},\mathrm{z}⟩:$

1. Reject if any of the three strings is not a binary number as stated above.

2. Create three binary counters pointing to the right $\mathrm{i},\mathrm{j},\mathrm{k}$, which represent the majority of$\mathrm{x},\mathrm{y}$ and correspondingly.

3. Using $\mathrm{i},\mathrm{j},\mathrm{k}$and a carry flag, do binary addition (bitwise long addition).

4. Reject if there is a difference between the estimated and real next bit of$\mathrm{z}$ .

5. Accept if you've reached the end of all three number representations and there's no mistake.

So ${\mathrm{M}}_1$runs in log space (it only needs three counters) and chooses to $\mathrm{ADD}"$.

Thus, the condition$\mathrm{ADD}\in \mathrm{L}$ has been proved.

The given language is,

$\mathrm{PAL}\_\mathrm{ADD}=\left\{⟨\mathrm{x},\mathrm{y}⟩\right|\mathrm{x},\mathrm{y}>0$are the binary integers where$\mathrm{x}+\mathrm{y}$ is an integer whose binary representation is a palindrome.

The condition is to prove that $\mathrm{PAL}\_\mathrm{ADD}\in \mathrm{L}$.

Let ${\mathrm{M}}_2$be the DTM that decides ADD in the logarithmic space.

The construction of${\mathrm{M}}_2$ is as follows:

${\mathrm{M}}_2="\mathrm{On}\mathrm{input}⟨\mathrm{x},\mathrm{y},\mathrm{z}⟩:$

1. Reject if any of the three strings is not a binary number as stated above.

2. The length$\mathrm{l}$ of$\mathrm{x}+\mathrm{y}$ in binary.

3. For$\mathrm{i}=1$ to$\raisebox{1ex}{$\mathrm{l}$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$ .

Compute the${\mathrm{i}}^{\mathrm{th}}$ bit of $\mathrm{x}+\mathrm{y}$.

Compute${(\mathrm{l}-\mathrm{i}+1)}^{\mathrm{th}}$ bit of $\mathrm{x}+\mathrm{y}$.

If $\mathrm{a}\ne \mathrm{b}$, then reject.

Thus, the condition$\mathrm{PAL}\_\mathrm{ADD}\in \mathrm{L}$ has been proved.