Let a match$-$TM be a Turing$-$Machine that doesn$$t have an accepting state or a

rejecting state. Instead it has a single halting state. If a match$-$TM ever enters the

halting state, it immediately stops computing. Then, if the current contents of the

$3$: Turing Machines$-3$

tape are exactly equivalent to the starting contents of the tape it accepts, otherwise

it rejects.

Show that match$-$TM$$s are equivalent in power to ordinary TM$$s$.$ Notice that this

proof has two directions