A decision problem for which no algorithm terminates with the correct yes-or-no answer on every input. For example, if the diagonal halting set had a decision algorithm, a program could halt on its own code exactly when that algorithm says it does not halt, producing a contradiction. An undecidable decision problem may still admit a partial procedure that terminates on every yes-instance.
Articles by others on the same topic
There are currently no matching articles.