3
$\begingroup$

I have a book that proves the halting problem with this simple statement:

$$ A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon $$

It states that halting problem reduces to the language consisting of $\langle M, \omega \rangle$ for which a Turing machine $M$ accepts $\omega$ is undecidable.

What does this mean? What does the notation $\le_m$ indicate?

$\endgroup$
  • $\begingroup$ Is $\text{HALTING}^\varepsilon$ is the language of all encodings of TMs that stop on the empty tape? $\le_m$ denotes a many-one reduction. $\endgroup$ – A.Schulz Nov 7 '12 at 20:49
  • $\begingroup$ Thanks! What's a many-one reduction? $\endgroup$ – David Faux Nov 7 '12 at 21:09
  • $\begingroup$ A many-one reduction from $L$ to $L'$ (given an alphabet $\Sigma$) is a (computable) function $f: \Sigma^* \to \Sigma^*$ such that for every $w \in \Sigma^*$, $w \in L$ if and only if $f(w) \in L'$. The "many-one" means that we allow $f(w) = f(w')$ (it's not injective). In your settings, it basically means that you can transform an input to $A_{TM}$ to HALTING such that the first accepts the input iff HALTING accepts the transformed input. $\endgroup$ – Pål GD Nov 7 '12 at 21:15
3
$\begingroup$

The symbol $\leq_m$ means many-one reducible, contrast to reductions such as turing reducible (denoted by $\leq_T$) and one-one reducible (denoted $\leq_1$).

A many-one reduction from $L$ to $L′$ (given an alphabet $\Sigma$) is a (computable) function $f:\Sigma^* \to \Sigma^*$ such that for every $w \in \Sigma^*$, we have that $w \in L$ if and only if $f(w) \in L′$. The "many-one" means that we allow $f(w) = f(w′)$ (it does not have to be injective). In your setting, it basically means that you can transform an input to $A_{TM}$ to $HALTING$ such that $A_{TM}$ accepts an input $w$ if and only if $HALTING$ accepts the transformed input $f(w)$.

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