Question: Use the macroinstruction searchright in Exercise to create a Turing machine program that replaces the symbol immediately to the left of the leftmost a by a blank. If the input contains no a, replace the rightmost nonblank symbol by a b.

Exercise: Give an implementation of the macroinstruction search right (a, q_i, q_j), which indicates that the machine is to search its tape to the right of the current position for the first occurrence of the symbol a. If an a is encountered before a blank, the machine is to go into state q_i, otherwise it is to go into state q_j.