1,023 views

Consider the following language $L$:
$L=\{<M,x,k> \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$
The language family to which $L$ belongs is not closed under?

1. Intersection
2. Homomorphism
3. Set Difference
4. Complementation

$\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.

No language [class] is closed under set difference? How come? $A - B = A \cap \overline B.$ Recursive family is closed under intersection and complement and so set difference too.

@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.

Is this table correct?