Redirected
edited by
3,367 views
3 votes
3 votes

Consider <M> be the encoding of Turing Machine as string over alphabet  $\Sigma$ = {0,1}.Consider L= { <M>| M is TM that halt on all input and L(M) = L` for some undecidable language L` . Then L is 

  1. Decidable and Recursive
  2. Decidable and non Recursive
  3. Undecidable and Recursive
  4. Undecidable and non Recursive
edited by

3 Answers

1 votes
1 votes
L = { <M>| M accepts w } is a halting problem. L is recursive enumerable but not recursive as on input w, M can either halt on w or enter into loop.

But L = { <M>| M halts on w } is a recursive language and decidable because there is no possibility of entering into loop. Thus L is not the halting problem.

Given, L= { <M>| M is a tm that halts on all inputs } and L(M) = L' for some undecidable language L' .

Let us assume <M'> ∈ L. Then L(M') is decidable. But according to given condition, L(M') = L' for some undecidable language. Hence this contradicts our assumption. Therefore <M'> ∉ L.
Thus L is an empty language. Hence L is regular and decidable.

Since, every regular languages are also recursive languages are also recursive languages.

Hence L is decidable and recursive.

Option a is correct.
1 votes
1 votes

Here is another approach to the problem:

We know that,

REC(or decidable) ⊂ REL(or undecidable or semi undecidable) ⊂ U(totally undecidable). Where U denotes the set of all languages possible. 

M halts on all inputs and hence surely that it will halt. Hence, decidable.

L(M) = L' such that L is undecidable. Taking complement and considering the set theory L' is decidable.

Intersection of it will give decidable language. Hence it is recursive.

Some answers states it to be regular. But I think, its recursive but we can’t be sure that it will be regular

0 votes
0 votes

Language L is undecidable => Recursively Enumerable Language.

RE languages are not closed under complement. So L' is not RE language.

Related questions