Turing Machine writes "a" for every input w is undecidable

I have a doubt on my solution of the following: Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all and only the Turing machines that write "a" on the tape for every possible input w prove that this language is undecidable.

Formalization: A={<M, a> | M is a Turing machine and M writes a for every input string w}

Proof of undecidability: Assume that A is decidable and H is it's decider, we can prove that there must exist a decider for ATM reaching a contraddiction.

On input <M, w>:

1. Build a Turing machine N as will follow
2. Run H on input <N, a>
3. Return the output

N=On input x:

1. Run M on w
2. If M accepts, write "a" on the tape and accept
3. If M rejects, write "a" on the tape and reject
4. If M loops, write "a" on the tape and reject

Is this correct? I am not sure if the construction of N is ok specifically in the point 4.

Your suspicion is well-founded. The point 4 is invalid.

Imagine the exact moment N "writes 'a' on the tape and reject" in the point 4. That means at that moment, it is known that M loops. However, all the algorithm has done is running M on w for some steps without acceptance nor rejection. It is possible that if we run M one step more, it will halt to accept or reject. So, it cannot be certain that M loops.

In fact, had point 4 been valid, we would have solved the halting problem by the simple Turing machine below.

On input <M, w>:

1. Run M on w
2. If M accepts or rejects, accept
3. If M loops, reject

Here is a proof of undecidability of A.

Assume that A is decidable and H is it's decider, the following will be a specification of a decider for ATM, which is known to be impossible, however.

On input <M, w>:

1. Build a Turing machine N as below.
2. Run H on input <N, a>
3. Return the output

N=On input x:

1. Run M on w
2. If M accepts, write "a" on the tape and accept
3. If M rejects, reject.

The section above interprets "M writes a" in the definition of A as "M writes 'a' and accept, leaving all other cells blank.". i.e., M returns "a".

Another interpretation of "M writes a" is that "M will write 'a' at least once during its execution". Then the construction of N will be more complex.

• Thank you sooo much! I was also uncertain of whetever it was correct to write "a" only when M accepts w so that got me confused, but now I see it's the only way!
– DRE
Jun 10, 2022 at 17:20