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

sor of its positive integer input. Both the input and the output are encoded on the

tape as their binary expansions $($without any leading $0$ s $,$ with the exception of $0$ it$-$

self$).$ 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 $1($decimal $1),$ yields the output $0($decimal $0)$ and

the input $100($decimal $4),$ yields the output $11($decimal $3).$

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 $110($decimal

and $1000($decimal $8).$

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.