Which of the following is/are undecidable?

PYQ GATE 2022

Which of the following is/are undecidable?

  1. A.

    Given two Turing machines M1 and M2 decide if L( M1) = L(M2)

  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

Attempted by 135 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…