The other possibility is that the machine encounters a \(1\) while in state so. You want to change this \(1\) to a \(0\), skip over any remaining \(1's\) as well as the asterisk, skip over any \(0's\) to the right of the asterisk (these represent parts of \({n_2}\) that have already been matched off against equal parts of \({n_1}\)), and then either find a \(1\) in \({n_2}\)) (which you change to a \(0\) ) or else come to the blank at the end of the input. Here are the transitions: \(\left( {{s_0},1,{s_1},0,R} \right),\left( {{s_1},1,{s_1},1,R} \right),\left( {{s_{1,}}{s_{2,}}R} \right),\left( {{s_2},0,{s_2},0,R} \right),\left( {{s_2},1,{s_3},0,\;L} \right),\left( {{s_2},\;B,{s_4}} \right.,B,L)\). At this point you are either in state \(83\), ready to go back for the next iteration, or in state \(84\) ready for some cleanup. In the former case, you want to skip back over the nonblank symbols until you reach the start of the string, so you add five-tuples \(\left( {{s_3}{,^*},{s_3}{,^*},\;L} \right),\left( {{s_3},0,{s_3},0,\;L} \right),\left( {{s_3},l,{s_3},l,L} \right)\), and \(\left( {{s_3},\;B,{s_0},\;B,R} \right)\). In the latter case, you know that the first string is longer than the second. Therefore, you want to erase remnants of the second input string and the asterisk, and change the \(0's\) in the first input string back to \(1's\). Here are the transitions: \(\left( {{s_4},0,{s_4},\;B,\;L} \right),\left( {{s_4}{,^*},{s_8},\;B,\;L} \right),\left( {{s_8},0,{s_8},l,L} \right),\left( {{s_8},1,{s_8},l,L} \right)\).
Therefore, the constructed Turning machine is:
\(\begin{array}{l}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,0,}}{{\bf{s}}_{\bf{0}}}{\bf{,0,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,}}{{\bf{s}}_{\bf{5}}}{\bf{,B,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{5}}}{\bf{,0,}}{{\bf{s}}_{\bf{5}}}{\bf{,B,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{5}}}{\bf{,B,}}{{\bf{s}}_{\bf{6}}}{\bf{,B,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{6}}}{\bf{,B,}}{{\bf{s}}_{\bf{6}}}{\bf{,B,R}}} \right){\bf{,}}\\\left( {{{\bf{s}}_{\bf{6}}}{\bf{,0,}}{{\bf{s}}_{\bf{7}}}{\bf{,l,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{7}}}{\bf{,0,}}{{\bf{s}}_{\bf{7}}}{\bf{,l,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{7}}}{\bf{,l,}}{{\bf{s}}_{\bf{7}}}{\bf{,l,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{0}}}{\bf{,l,}}} \right.\left. {{{\bf{s}}_{\bf{1}}}{\bf{,0,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{1}}}{\bf{,l,}}{{\bf{s}}_{\bf{1}}}{\bf{,l,R}}} \right){\bf{,}}\\\left( {{{\bf{s}}_{\bf{1}}}{\bf{,}}{{\bf{s}}_{\bf{2}}}{{\bf{,}}^{\bf{*}}}{\bf{,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{2}}}{\bf{,0,}}{{\bf{s}}_{\bf{2}}}{\bf{,0,R}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{2}}}{\bf{,l,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{2}}}{\bf{,B,}}{{\bf{s}}_{\bf{4}}}{\bf{,B,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{3}}}{{\bf{,}}^{\bf{*}}}{\bf{,}}{{\bf{s}}_{\bf{3}}}{{\bf{,}}^{\bf{*}}}{\bf{,L}}} \right){\bf{,}}\\\left( {{{\bf{s}}_{\bf{3}}}{\bf{,0,}}{{\bf{s}}_{\bf{3}}}{\bf{,0,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{3}}}{\bf{,l,}}{{\bf{s}}_{\bf{3}}}{\bf{,l,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{3}}}{\bf{,B,}}{{\bf{s}}_{\bf{0}}}{\bf{,B,}}} \right.{\bf{R),}}\left( {{{\bf{s}}_{\bf{4}}}{\bf{,0,}}{{\bf{s}}_{\bf{4}}}{\bf{,B,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{4}}}{{\bf{,}}^{\bf{*}}}{\bf{,}}{{\bf{s}}_{\bf{8}}}{\bf{,B,L}}} \right){\bf{,}}\\\left( {{{\bf{s}}_{\bf{8}}}{\bf{,0,}}{{\bf{s}}_{\bf{8}}}{\bf{,l,L}}} \right){\bf{,}}\left( {{{\bf{s}}_{\bf{8}}}{\bf{,l,}}{{\bf{s}}_{\bf{8}}}{\bf{,l,L}}} \right)\end{array}\)
