MadeEasy Subject Test 2019: Theory Of Computation - Decidability

Question

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

Comments

I have edited the question to remove any ambiguity. There's nothing more to explain in this than what Ankit did.

---

@Arjun Sir

if u change L to D, then L' also need to be D'

right?

Otherwise what is L' ??

---

$L$ was not there -- now see.

Answer 1

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.

Comments

@SuvasishDutta

chk it

https://gateoverflow.in/blog/5578/decidability?show=5589

https://gateoverflow.in/70127/halting-problem-of-turing-machines?show=71713

Only accepts doesnot tells halting problem

right?

There is no C program that reads a C program P and input w, and decides ifP “accepts” w.

The proof of the above theorem is identical to the halting theorem - we just perform our rewriting on the C program.

Also, notice that being able to recognize a language and its complement implies that the language is decidable, as the following theorem testifies.

---

Halting problem is problem of determining whether an arbitrary program on a certain input will halt on enter into loop forever.
For an arbitrary turing machine, whether tm will halt on certain input or loop is same as halting problem. That is why acceptance of a certain word or string by a turing machine is undecidable as it is same as halting problem.
But in this question, it is mentioned that tm halts on all inputs. That's why it is decidable and not same as halting problem.

---

Are you sure about this? And if yes, then can you please define the membership problem.

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.

 

Answer 2

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

Answer 3

Language L is undecidable => Recursively Enumerable Language.

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