reduction from ALLtm to Etm

619 views Asked by At

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.

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

(If w∈L(M) M1 rejects it, so if L(M)=∑*, L(M1)=∅.

If w∉L(M) (M doesn't stop on w or rejects) M1 accepts w, so if L(M)≠∑*, L(M1)≠∅).

0

There are 0 answers