The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

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 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?
(edited 3 years ago)

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you