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.