777 views
4 votes
4 votes

Given TMs M_{1},M_{2},M_{3},.......M_{n} and L = {x/Every M_{i} halts on input x } which of the following is true about L?

(A) L is recursively enumerable but not recursive

(B) L is Recursive but not Context free

(C) L is Not Recursively Enumerable

(D) L is regular 

3 Answers

Best answer
2 votes
2 votes

A string x is the member of the language L, if all the turing machines M1, M2, ... Mn halt on that string.


Suppose, there is a string, let's take  0101, if all the TM halt on it, means they either accept or reject it then 0101 is a member of the language L.

Assume, there is another string, let's take 1010101 on which any TM doesn't halt, then neither we can accept 1010101 as a member of the language L nor we can reject it.

(A) is correct answer!

6 votes
6 votes

Answer is (A)

L is the collection of all strings for which $M_1$,$M_2$,...$M_n$ Halts on. I.e, They come to stop either by accepting or rejecting. As we can see, there is a chance that it can also go into an infinite loop. This is same as the halting problem and the language is R.E but not Recursive.

edited by

Related questions

2 votes
2 votes
1 answer
2
smartmeet asked Feb 7, 2017
881 views
A B-tree of order m is a tree which satisfies the following properties:Every node has at most m children.Every node (except root) has at least ⌈m/2⌉ children maximi...