Given Language is REC or Non RE

Question

Which of the following is true for the given language?

$L=$ {<TM> | TM halts on every input}

<TM> is encoding of the Turing machine

(A) $L$ is Recursive and $\overline{L}$ is also Recursive

(B) $L$ is Recursive Enumerable and $\overline{L}$ is also Recursive Enumerable

(C) $L$ is Non Recursive Enumerable and $\overline{L}$ is Recursive Enumerable

(D) $L$ is Non Recursive Enumerable and $\overline{L}$ is Non Recursive Enumerable

Comments

Here we are given a language which is described in terms of encoding of TM. Nothing is told whether the TM for the given language is halting or not. It is same as asking whether a given program halts on all inputs.

Only if you understand this, you can understand the solution. But if you understand the question properly you can say L is not recursive. Whether recursively enumerable or not is the real question

---

Please explain. Does the question itself states that TM for L halts on every input bcoz if it is given then L will be REC and correct choice will be option (a). Or does it ask us to prove whether TM halts on every input for some L for which option d will be correct choice as it is standard halting problem of TM

---

@Arjun sir they already mentioned it that it will halt for every input then  it should be recursive and complement of recursive language is also recursive then option A should be the correct

Answer 1

Well, there is an easy solution to this- thanks to @Sonu.

L here describes the encoding of TM which halts for all inputs. In other words, L describes the encoding of TMs whose language is recursive. Now, this problem can be solved easily using Rice's theorem. (part 2).

L(TM) is recursive?  is a non-monotonic property, because we have a TM for which L(TM) is recursive - TM_yes, and we can have another TM for which L(TM) is non-recursive- M_no and L(TM_yes) subset of L(M)_no. (For example L(TM_yes) is ∅ and L(TM_no) is any non-recursive language). Now, all non-monotonic property of language of TM are not-even semi decidable- their language is not recursively enumerable. So, L is not recursively enumerable. 

L' can be stated as is L(M) non-recursive? This is again a non-monotonic property as we can have L(TM_yes) = a non recursive language and L(TM_no) = Σ*, so that the subset condition holds. So, L' is also non-recursively enumerable. 

 

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

Comments

Sir is this me in ur above comment

---

that you should know better :)

---

A big thanks to you Sir. Cleared every doubt of mine regarding this topic. :)

Answer 2

The question describes a language which has the encoding of the TMs that halts for every input. Now, to say this language is recursive, we have to make another TM (this new TM is different from the encoding of TMs in L) which accept all strings in L (which are encoding of all halting TMs). If this new TM halts for all input, then the given language is recursive. If it halts for strings in L (may or may not halt for strings not in L), then the given language is recursively enumerable. 

(The given property is of TM and not its language. So, we can't use Rice's theorem )

So, only way is reduction. If we reduce halting problem to this problem (solve halting problem assuming solution to given problem), then we prove that L is not recursive as language of halting problem is proved to be non recursive. 

First we try to solve halting problem. We assume we have a TM M for accepting L, that is given an encoding of a TM, our TM will say "yes" if the encoded TM halts for all inputs and "no" otherwise. Now, we want to solve halting problem using this. Halting problem is to decide if a given TM halts for a given word w. We proceed as follows:

Given an instance of halting problem (an encoding of a TM H and a word w), we make another TM N which will take any input but simply erases that input from the input tape and simulates the moves of H on w. If H halts on w, N halts on all inputs. If H doesn't halt on w, N won't halt on any input - reduction is perfect. Now, we simply give the encoding of N to our assumed TM for L- M. If L says "yes"- we can say H halts on w, if L says "no"- we can say H does not halt on w - we have solved halting problem, which can never be done. Thus, our assumption is wrong and such an M can't exist. So, L is not recursive. 

To prove L is not RE is bit more tricky. One proof is given here:

http://www.inf.ed.ac.uk/teaching/courses/ci/documents/note09.pdf

To prove L' is not recursively enumerable: (It's easier as we can directly reduce from complement of halting problem)

$L' = \left\{<TM> \mid \text{ TM does not halt on some input } \right\}$

We can try reduction from complement of halting problem. Complement of halting problem is given a TM H and a word w, we have to say if H does not halt on w. We proceed as follows: (same reduction as done for halting problem).

We assume we have a TM M' which semi-decides L'- that is it says "yes" if we give encoding of a TM that does not halt on some input. (It may say "no" or loops, if the encoded TM halts on all inputs)

Given an instance of complement of halting problem (an encoding of a TM H and a word w), we make another TM N which will take any input but simply erases that input from the input tape and simulates the moves of H on w. If H halts on w, N halts on all inputs. If H doesn't halt on w, N won't halt on any input - reduction is perfect. Now, we give the encoding of N to our assumed TM for L'- M', and if M' says "yes", it means N does not halt on some input- possible only if H does not halt on w - we solved complement of halting problem using M' which is not possible. So, M' cannot possibly exist meaning L' is not recursively enumerable.

So, L is not recursive and L' is not recursively enumerable. The only matching option is (D) - we need not prove L is not RE. 

Comments

The main part is in understanding the question- The questions describes a language L which contains the encoding of TMs which halts for all inputs. Now, is this language recursive? (Its like asking you to write a program which takes another program as input and to tell if that input program halts for all its inputs)

To prove that this is not recursive, we use the TM for this language to solve halting problem. If we do that, that means such a TM cannot exist and hence L is not recursive.

---

what is meant by “encoding” of TMs?

---

When you write a C code, even though you write using English alphabets it is encoded in binary once saved to disk. Likewise a Turing machine description can be given using mathematical symbols or English language and this can be encoded in binary or any other coding so as to give as input to a machine which has the corresponding decoding capability.