HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemundecidablecomputablehaltingalgorithmdecisionthatforthereleads

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#28727, answer score: 4

Revisions (0)

No revisions yet.