2,981 views

2 Answers

4 votes
4 votes

This question basically tests your knowledge of the words "accept", "halt" and "reject" in context of Turing Machines.

Turing Machines can accept a language in just one way — halting.

Turing Machines can reject a language in two ways — 1) falling in an infinite loop. 2) Halting (and saying "no")

 

If M1 doesn't halt on a language, ie, it rejects the language by falling in an infinite loop; M2 can possibly reject it by halting.
Option A eliminated.

If M1 halts on an input to reject the string, M2 might reject it by infinite loop.
Option B eliminated.

Whatever string M1 accepts, M2 accepts it, too. Hence, M2 halts on it.
Option C is correct.

2 votes
2 votes
Given M1 and M2 are Turning machines and their languages are same, meaning they must accept all string in their respective languages and reject or loop forever for the strings not in the language. So, if both are having same language, both must accept the same set of strings. i.e., C option is TRUE or even strongly we can say that on every i/p which M1 accepts, M2 must also "ACCEPT" (accept means halt also happened). Options A and B are not true because for strings not in the language TM may reject (hence halt too) or loop forever. Had the given TM been halting TM (whose language is recursive), then options A, B and C would have been TRUE.

Related questions

0 votes
0 votes
0 answers
1
3 votes
3 votes
3 answers
2
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4