Construct a Turing Machine, with input alphabet $\{0,1\}$ that computes the successor

of its natural number input. Both the input and the output are encoded on the tape

as their binary expansions $($without any leading $0$s$).$ At the start of the computation,

the tape head points to the leftmost bit of the input. At the end of the computation,

the tape head should point to the leftmost bit of the output. For example,

the input $0($decimal $0),$ yields the output $1($decimal $1),$ and

the input $111($decimal $7),$ yields the output $1000($decimal $8).$

You must specify the tape alphabet for your machine. This tape alphabet must con$-$

tain $\{B,0,1\},$ and can contain more.

In your submission, include all of the following.

i$.$ A brief description of the algorithm. This description may include pseudo$-$code.

ii$.$ The transition diagram for the machine.

iii. A description of how the states and their transitions implement the brief de$-$

scription.

iv$.$ Show the entire Turing Machine computations on the input words $11($decimal

and $101($decimal $5).$

Write your solution neatly. Marks may be deducted if a grader cannot easily under$-$

stand your solution and why it works $-$ even if it is actually correct.