## Show that the problem of whether a Turing machine, when started on a blank tape, ever writes a given symbol (say a) of its input alphabet on its tape is not decidable

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.