UTpaper

Free mock tests & test series

Question 140Asked in BPSC TRE 3.0 (2024) Computer Science Class 11-12

What is the computational complexity of the halting problem?

  1. AO(1)
  2. BO(n)
  3. CNot computable
  4. DMore than one of the above
  5. ENone of the above
Show answerHide answer

Correct answer: (C) Not computable

Explanation

Turing proved the halting problem is undecidable: no algorithm can decide for every program and input whether it halts. So it has no computational complexity; it is not computable.

From BPSC TRE 3.0 (2024) Computer Science Class 11-12 — Previous Year Paper

This is question 140 of BPSC TRE 3.0 (2024) Computer Science Class 11-12 — Previous Year Paper. See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.