Let $=\{1,1,,$ #$\}.$ Provide a formal level description of a input$-$output TM

computing the following function$\mathrm{.}1$

On input w in $,$ find the first occurrence the substring $1$#$,$ replace that $1$ with

a $1,$ and insert a $$ right before the # $($pushing the rest of the string to the right$).$

If w did not have any such substring, change nothing $($output w$).$

For example, on input #$11$#$$ #$,$ the output should be #$11$ #$$ #$.$

Don$$t forget to give an informal explanation of how your TM works $($a formal

proof not required$).$

$($b$)$ Provide the complete sequence of configurations of your TM when started on the

above example input, #$11$#$$ #$.$

Note $($not necessary for solving the above$)$: the motivation for this question is that

this is a simplified version of one of the steps we would implement when simulating a

k$-$tape TM with a single tape TM as we did in class $($the edge case where we move

to the right but see a # telling us we need to insert a blank before it$,$ as the reading

head in the multi$-$tape TM now points to a blank from the infinite portion we had not

previously readched$)$