Dark Mode

1,023 views

3 votes

Best answer

$\text{L={<M,x,k>∣M is a Turing Machine and M does not halt on x within k steps}}$

L is a recursive language, There are 3 inputs TM, K and x to the UTM, we can run the UTM for a given input and find whether the given TM halts on x with in k steps, if it halts we can ignore it and if it doesn't then we can keep it inside our language.

Hence, it's possible to make a total Turing machine for this language, so it's a $Decidable$ problem, So,** L is recursive**.

Recursive languages are not closed under $Homomorphism$, So, **(B) is the correct option**!

__Note that__, Recursive languages are closed under $intersection$ and $complement$, and $A-B = A∩B'$ Hence, Recursive languages are closed under set difference.

3

@Arjun sorry :( i confused set difference with subset property :(, yes every language which is closed under intersection and complement will be closed under set difference.

0