Polynomial Reduction Example

Show that WRITE_ONE_TM = {M : M is a Turing machine that writes a 1 on its tape } is undecidable.

Let us assume that WRITE_ONE_TM is decidable. Then there exists a Turing machine WRITE_ONE_TM,  which can tell you if a given Turing Machine M will write a 1 on its tape on input z.

Let us look at how WRITE_ONE_TM  works.

M is the input to WRITE_ONE_{TM .}

If M writes a 1 on its tape , WRITE_ONE_TM  accepts.  – Yes instance

If M does not write a 1 on its tape, WRITE_ONE_TM  rejects. – No instance.

If M writes a 1 on its tape at any time of its computation, WRITE_ONE_TM decides yes. It does not matter what M does before it writes 1 on its tape.

 M might have 10000 transitions before it writes 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

M might compute what is 5+7 before it writes 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

M can watch a youtube video and then write a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write 1 on its tape.

( just kidding)

M might simulate another Turing Machine and then write a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write a1 on its tape.

Suppose M is simulating another machine T on input w on M’s tapes and if T accepts w, M is writing a 1 on its tape. Still WRITE_ONE_TM should be able to decide whether M will write a1 on its tape.

Did you hear that?

Isn’t that a solution to decidability of A_TM. Whenever you have to decide if a TM T will accept or reject w, all you have to do is:

Construct a new TM, M such that

·        It simulates T on input w on M’s tape

·        If T accepts w, write a 1 on M’s tape.

·        Feed M to WRITE_ONE_TM

·        If WRITE_ONE_TM decides yes, T accepts w.

    

But we already know that A_TM is undecidable. So it is not possible that WRITE_ONE_TM  can be decidable if it can solve A_TM.

Hence WRITE_ONE_TM  is undecidable.