2
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

All decidable problems can be reduced to the halting problem, since you can build a machine that solves the problem in bounded time and place (even if the bound was super exponential) and accepts if the output is yes else it goes into a loop.

A more interesting example is the post correspondence problem. It is a well-known undecidable problem. The proof is basically a reduction from the Halting problem. Here I present a reduction in the other direction, namely from the post correspondence problem to the halting problem.

First let us define the problem. Given two sets of words $A := \{a_1, \dots a_n\}$ and $B := \{b_1, \dots, b_m\}$ over an alphabet of size at least two. Is there a sequence $i_1, \dots i_l$ and $j_1, \dots j_{l'}$ such that the strings resulting from concatenating $a_{i_1}a_{i_2}\dots a_{i_l}$ is equal to the sting $b_{j_1}\dots b_{j_{l'}}$.

For a reduction to the halting problem, given an instance $I$ of the post correspondence problem, we build a touring machine $M$, such that the instance is a yes-instance if and only if the machine halts by the empty input (The machine totally ignores the input band).

For each positive integer $k$, the machine simulates all strings that result from concatenations of at most $k$ strings in $a$ and all strings that result from concatenations of at most $k$ strings in $b$ and check if any resulting string from the first set is equal to any resulting string from the second set.

If the machine halts at some value of $k$, this means there is a string of at most $k$ strings from $a$ that can be written as a concatenation of at most $k$ strings from $b$ and hence the given instance is a yes instance.

On the other hand, if the given instance is a yes-instance, for $k = max\{l, l'\}$, the machine halts in the $k$-th iteration.

$\endgroup$
0
$\begingroup$

Before Fermat's Last Theorem was proved, it could easily be reduced to the halting problem: You can easily write a program that will halt if and only if there are 1 ≤ a ≤ b ≤ c, and n ≥ 3, such that $a^n + b^n = c^n$. A proof that the program halts or not would have proved that FLT is wrong or right. And a solution to the halting problem (a program that can decide whether an arbitrary other program halts or not) would have been able to prove or disprove FLT.

$\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.