🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Decidability and Complexity: all 10 questions

Quiz: Decidability and Complexity · Question 6 of 10

The halting problem is:

The halting problem is:

  1. A.Decidable and recognisable
  2. B.Recognisable but not decidable
  3. C.Neither recognisable nor decidable
  4. D.Decidable but not recognisable
Answer & explanation

Correct answer: Recognisable but not decidable

Run P on w and accept if it halts; that recognises HALT, but no program decides it.

Can you get the rest right without peeking?

Take the timed Quiz: Decidability and Complexity quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →