I am trying to understand why this "proof" of ETM undecidability is wrong.

ALLTM={ < M >|M is a TM, L(M)=∑*}

ETM={< M >|M is a TM, L(M)=∅}

We know that ALLTM is undecidable, lets assume ETM is decidable (T is a TM that decides ETM) and get a contradiction.

 S= "On input < M >, M is a TM:

  1.Construct the following TM M1,

   M1=" On input x:

    1.Run M on x, if M accepts x, reject. otherwise, accept x."

    2.Run T on input < M1 >.

    3.If T accepts, accept, if T rejects, reject.

If ETM is decidable, ALLTM is decidable => ETM is undecidable.

Why this reduction doesn't prove that ETM is undecidable?

  • $\begingroup$ The only problem that I see (apart from formatting) is that $T$ is undefined. I think you want to let $T$ be a Turing machine that decides ETM. $\endgroup$
    – Steven
    Nov 22 '20 at 16:40
  • $\begingroup$ It's part of the proof, I've added it. $\endgroup$
    – Dan
    Nov 22 '20 at 17:40
  • $\begingroup$ The proof seems fine , can you tell us why you believe it is incorrect or whether is is stated somewhere that this proof is incorrect ? $\endgroup$
    – Anazz
    Nov 22 '20 at 18:38
  • $\begingroup$ It's part of our course material, and was presented as a fact. I thought that there maybe a problem reducing from and to an unrecognized language but I can't find any reference. $\endgroup$
    – Dan
    Nov 22 '20 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.