GATE CS 2022 (Forenoon) — Question 46

Theory of Computation (TOC)Turing Machines & UndecidabilityMSQ2 marksMedium

Which of the following is/are undecidable?
  1. A
    Given two Turing machines \(M_1\) and \(M_2\), decide if \(L(M_1) = L(M_2)\).
  2. B
    Given a Turing machine \(M\), decide if \(L(M)\) is regular.
  3. C
    Given a Turing machine \(M\), decide if \(M\) accepts all strings.
  4. D
    Given a Turing machine \(M\), decide if \(M\) takes more than 1073 steps on every string.
Practise the full 2022-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.
Practise more on Turing Machines & UndecidabilityTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group