in Theory of Computation
79 views
0 votes
0 votes

There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Lis a non-Recursively Enumerable Language.

Now Ld can be reduced to the problem ATM (Universal Language) as follows "To see if w ∈ Ld check if <w, w> ∈ ATM."

The theorem 9.7 (Page 393) in Hopcroft Ullman states that if there exists a reduction from P1 to P2, then: if P1 is non RE then so is P2.

According to this theorem, since Lcan be reduced to ATM, and Lis non-RE, ATM must be non-RE. But we know that ATM  is Recursively Enumerable and undecidable. How is this possible?

in Theory of Computation
by
79 views

Please log in or register to answer this question.

Related questions