theory of computation

Question

This language,

L = { <M,w> / M is a TM,w is a string and M does not halt on string w }

is not recursively enumerable ...right ???

Comments

Recursive language : Language accepted by a halting TM.

When a string belonging to Recursive language is given to halting TM/ TM , the TM will say that the given string is present in the Language and halts.

When a string not in Recursive language is given to halting TM, the TM will say that the given string is not present in Language and halts.

 

Recursively Enumerable language: Language accepted by TM.

When a string belonging to Recursive language is given to TM , the TM will say that the given string is present in the Language and halts.

When a string not in Recursive language is given to  TM, the TM will not halt instead it enters a loop.

Since M does not halt on w, and language L is defined over this TM, the language accepted by this TM is Recursively Enumerable language.

I think L is recursively enumerable language. Correct me if iam wrong.

---

Yes, it is non RE .

---

@Kapil,

 Please explain

---

This is the complement of halting problem. Any TOC book should have reason why this is not r.e. If this problem is r.e., then halting problem becomes decidable.

---

Thank you.

Answer 1

it is recursive because there is an answer for the string that whether it will halt or not ;

but in recursive enumrable language we know only if it will be acceptable and there is no decidebility for yes or no .