← Quiz: Decidability and Complexity: all 10 questions
Quiz: Decidability and Complexity · Question 6 of 10
The halting problem is:
The halting problem is:
- A.Decidable and recognisable
- B.Recognisable but not decidable
- C.Neither recognisable nor decidable
- 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 →