3
$\begingroup$

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that the converse is true for a decision problem in RE complexity class, but not for the other way around.

$\endgroup$
4
$\begingroup$

Let me rephrase your question. Suppose $O$ is undecidable; can Turing machines with an $O$-oracle solve the halting problem? There are some undecidable $O$ for which this is false. Constructing such $O$ is known as Post's problem, solved using the priority method; Wikipedia has some details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.