patternMinor
Are there any problems that reduce to the halting problem?
Viewed 0 times
problemtheareanyhaltingproblemsreducethatthere
Problem
I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where P is some other language, but is there an example of another language that reduces to $A_{TM}$ (i.e if we could decide $A_{TM}$ then we could decide that problem)
Solution
Trivially every computable problem is reducible to $A_{TM}$. On the other extreme, there are plenty of problems which are $A_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A_{TM}$ - for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input $0$}\}$$ is Turing-equivalent to $A_{TM}$.
A more interesting situation arises when we ask about strict reducibility:
Is there a problem $X$ such that $(i)$ $X$ is not computable, $(ii)$ $X$ reduces to $A_{TM}$, but $(iii)$ $A_{TM}$ does not reduce to $X$?
The answer to this question was shown to be yes by Kleene and Post, although interestingly no natural examples are known (and indeed it's generally believed that none exist). This led to a natural follow-up question ("Post's problem"):
Is there a computably enumerable $X$ with the above properties?
This turned out to be much harder to solve, and wound up taking more than a decade; Friedberg and Muchnik independently introduced the priority argument to show that the answer is yes.
Today priority arguments - indeed, ones vastly more complicated than the original Friedberg/Muchnik theorem - are one of the main techniques in computability theory. They originally went by excitingly violent names: finite injury (Friedberg/Muchnik falls into this category), infinite injury (introduced by Sacks), and monstrous injury (introduced by Lachlan). While the first two terms are still in use, the third is not, and we categorize priority arguments more complicated than "basic infinite injury" according to the complexity of an associated set (the "true path"); in particular monstrous injury arguments are now called 0'''-arguments.
A more interesting situation arises when we ask about strict reducibility:
Is there a problem $X$ such that $(i)$ $X$ is not computable, $(ii)$ $X$ reduces to $A_{TM}$, but $(iii)$ $A_{TM}$ does not reduce to $X$?
The answer to this question was shown to be yes by Kleene and Post, although interestingly no natural examples are known (and indeed it's generally believed that none exist). This led to a natural follow-up question ("Post's problem"):
Is there a computably enumerable $X$ with the above properties?
This turned out to be much harder to solve, and wound up taking more than a decade; Friedberg and Muchnik independently introduced the priority argument to show that the answer is yes.
Today priority arguments - indeed, ones vastly more complicated than the original Friedberg/Muchnik theorem - are one of the main techniques in computability theory. They originally went by excitingly violent names: finite injury (Friedberg/Muchnik falls into this category), infinite injury (introduced by Sacks), and monstrous injury (introduced by Lachlan). While the first two terms are still in use, the third is not, and we categorize priority arguments more complicated than "basic infinite injury" according to the complexity of an associated set (the "true path"); in particular monstrous injury arguments are now called 0'''-arguments.
Context
StackExchange Computer Science Q#117537, answer score: 3
Revisions (0)
No revisions yet.