Assume the problem was decidable. Then there must be a total Turing machine Ma deciding it. We shall use Ma to build a new total Turing machine M∈ deciding the problem of acceptance of ∈ . (Since the latter is known to be undecidable, we shall conclude that the present problem is also undecidable.)
We construct M∈ which, on input ˆM , converts ˆM to ˆM 0 such that M’ is like M but:
• a is renamed to a new letter which is added to the alphabet of ˆM’ ,
• a new state q is added, which becomes the accepting state of ˆM’ , and
• transitions δ(t, b) = (q, a,R) are added for every b∈ T.
Then rewind and run as Ma on ˆM’ .
We can now deduce:
M∈ accepts ˆM <=> Ma accepts ˆM’ {Def. M∈ and ˆM}
<=>M’ reaches t starting from ∈ {Def. Ma and ˆM’}
<=>M accepts ∈ { Def. ˆM’}
So, M∈ decides the problem of acceptance of ∈. Since the latter is known to be undecidable, we conclude that the present problem is also undecidable.