How do we show that the following language is undecidable

Question

How do we show that the following language is undecidable.

(https://i.stack.imgur.com/In68J.png)

I am not really sure where to start for the proof. Probably using one of A_TM, HALT_TM, or E_TM to help because they are all undecidable. I can do those undecidability proofs so just using them with the assumption of being undecidable in the proof is fine.

Answer 1

The simplest method is probably reduction from the halting problem.

That is, you need to describe a simple transformation (think algorithm) X from an arbitrary TM, call it A, into a new machine M, s.t. if you did have a way of determining whether M ever writes a given string a on the tape, it would tell you whether A halts.

Another way of putting this is that X must guarantee that A halts if and only if M ever writes a on the tape. You get to pick any a you like.

Since with X in hand you have a solution to the general halting problem - which is known undecidable - the given language is also undecidable.