retagged by
1,620 views
4 votes
4 votes

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
retagged by

1 Answer

Best answer
3 votes
3 votes

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

selected by
Answer:

Related questions

5 votes
5 votes
2 answers
1
sh!va asked May 7, 2017
6,786 views
If $L$ and $P$ are two recursively enumerable languages then they are not closed underKleene star $L^*$ of $L$Intersection $L \cap P$Union $L \cup P$Set difference
0 votes
0 votes
1 answer
3
3 votes
3 votes
2 answers
4