Question

Construct a Turing machine, with input alphabet {0,1}, that reverses its input. Additionally, it should insert a blank at the left end of the tape, and accept, leaving the head at that cell.

For example, if the original tape is q₀10111, the final tape should be rB11101, for some state, r.

In your submission, include the following.

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

ii. A diagram of the transition function of the machine.

Make it neat - this may require re-drawing your early attempts.

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

iv. Show the entire computation on the input 110.

(reference CS245 20s A7)