Question $1.$ List the $7$ missing configurations in the computation history of the Turing machine In the picture $($a Turing decider for $\{w$#$w|win\{0,1{\}}^{**}\})$ on the input $01$#$01.$

High$-$level algorithmic idea: Zig$-$zag across the tape to corresponding positions on either side of the # symbol to check whether these positions contain the same symbol. If not, or it no # is found, reject. Cross off symbols as they are checked to keep track. When all symbols to the left of the # have been crossed off, check for any remaining symbols to the right.

Low$-$level pseudocode and state diagram defining formal machine:

Turing decider $M=(\{q_1,$dots,$q_8,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}}\},\{0,1,$#$\},\{0,1,$#$,x,\},,q_1,q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}},q_{\text{r}\text{e}\text{j}\text{e}\text{c}\text{t}})$

While tape head is $0$ or $1$ :

Replace tape head $b$ with $x$ and move $R.$

Scan $R$ for as long as the tape is $0$ or $1.$

If tape head $=$ : reject $.$

Move $R$ past # and scan $R$ past every $x.$

If tape head $b$ : reject.

Replace $b$ with $x$ and move $L.$

Scan $L$ until # and then until first $x.$

Move $R$ to the next unmatched character.

If tape head $=$ #:

Move $R$ and scan $R$ until next non$-x.$

If tape head $=$: accept.

Else: reject.

Complete the seven missing configurations in the computation history of $M$ on input

$\backslash$table$[[$start config,first match,second match,final scan,accept config$],[,C_2=x{q}_{2}1$#$01,C_9=,,],[,C_3=x1q_2$#$01,C_{10}=,,],[,C_4=x1$#$q_{4}01,C_{11}=,C_{16}=$#$q_8,],[C_1=q_{1}01$#$01,C_5=x1q_6$#$x1,C_{12}=,C_{17}=$#$x{q}_{8}x,C_{19}=$#$q_{\text{a}\text{c}\text{c}\text{e}\text{p}\text{t}}$