Turing machine

Question

If L is accepted by TM, which halts on every string over alphabet {a, b}, then L′ is recursive language.

True or False ?

I think false because L′ = TM halts on no string in {a,b} = $\phi$ and L(TM) = $\phi$ is non RE, let alone it being recursive

Comments

@just_bhavana it is given that TM halts on every string over {a,b} but it is not given that TM accepts all the string over {a,b}.

Suppose L is property which is of type $a^nb^n$ then all the string which satisfying this property will be in L and all other strings not satisfying this property will not be in L, means all those string which is not satisfying this property will be in L'. And it is given that TM HALTS (not specifically telling accepts) on every string over {a,b} which includes L and L'. So TM will always halt irrespective it is satisfying the property L or not. So it is Recursive.

---

thank you @Shubhanshu, got it now. Key point here was TM may halt in non final state also thus rejecting strings in L'

---

Yes, they are just asking for TM Halts not accepting.

Answer 1

It should be RECURSIVE....

what they said is ...L is a language which is accepted by TM ...means it may be REL or RECURSIVE...

the next statement itself indicate one thing...TM halts on every string over alphabet {a,b}...means if given string belong to L then Tm halts and if string does not belong to L then also TM halts ....

means L must be recursive ...

and if L is recursive then L complement is also recursive....

so its TRUE.

Comments

exactly, because we already have a halting tm which accept a language L, thus L has to be recursive and therefore complement of L is always be recursive.