# reduction from ALLTM to ETM

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?

• 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. Nov 22 '20 at 16:40
• It's part of the proof, I've added it.
– Dan
Nov 22 '20 at 17:40
• 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 ? Nov 22 '20 at 18:38
• 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.
– Dan
Nov 22 '20 at 19:56