160 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?

Please log in or register to answer this question.

Related questions

249
views
0 answers
0 votes
admin asked Oct 19, 2019
249 views
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
328
views
0 answers
0 votes
admin asked Oct 19, 2019
328 views
Give an example of an undecidable language $B$, where $B \leq_{m} \overline{B}$.
932
views
0 answers
3 votes
Nymeria asked Jan 10, 2018
932 views
a) L is decidableb) L is undecidablec) L is regulard) None of these
272
views
0 answers
0 votes
admin asked Jul 21, 2019
272 views
Show that the following problems are not recursively enumerable:The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.The set ... language of the first is the concatenation of the languages of the two $TM's$.