GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 26

Question

Which of the following languages is/are recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices)

 

• A. $L = \{\langle M \rangle \mid M \text{ moves its head left on input } w\}$
• B. $L = \{\langle M,x \rangle \mid x \text{ is prefix of } \langle M \rangle\}$
• C. $L = \langle M \rangle \mid M \text{ does not accept any string }w \text{ such that }001\text{ is a prefix of } w\}$
• D. $L = \{\langle M \rangle \mid \text{ there exists a TM } M_0\text{ such that } \langle M \rangle \neq \langle M_0 \rangle \text{ and } L(M) = L(M_0)\}$

 

Answer 1

A is recursive (decidable) as without doing a left move a Turing machine cannot do an infinite number of configurations and so we can always say "yes" or "no" after a finite number of moves.

B is just string comparison checking if $x$ comes as a prefix in the encoding of $M.$ Can be done with an LBA and hence $L$ is recursive.

C is a non trivial property of language of Turing machines and hence as per Rice's theorem $L$ is not recursive. Reference: https://gatecse.in/rices-theorem/.

D is saying for a given Turing machine we have another Turing machine which accepts the same language. This is true for any Turing machine and so $L$ accepts any Turing machine description making it regular (hence recursive too) as a valid Turing machine configuration can be detected using a finite automaton.

Correct answer: A; B; D.

Comments

@Omi Kakadiya I don’t quite know where you can find that very particular expression for the number of moves of the read/write head, in such a scenario. I just tried to analyze my through the given setup, and tried taking the help of the pigeonhole principle. Let me know if you don't quite agree with anything in the above approach.

Oops!!

---

@John_Smith I still feels something is wrong because won’t it might happen that , expression time loops may run and then in some of the future steps it may go to left 

---

@Omi Kakadiya Yes, you are right. I think the expression is true only for small sized inputs. Nevertheless, I have found the correct expression for the number of moves from a university handout (https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf , page no. - \(9\), question - \(9. \ (b)\)) mentioned in the reference section of https://gatecse.in/rices-theorem/ . Let me modify my above comment, and post that instead.

Answer 2

Options A and B are on Machine so we can’t apply the Rice theorem to it.

So, we have to check manually → “best explanation by gatecse answer”

Why Option C is false,

Reason → If you apply dovetailing, then within the finite time we can decide whether a string w belongs to language or not, but the twist is we have to check for all such w. which is infinite.

So, we can conclude that dovetailing can’t help us, hence Option C is not recursive.