Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  A.Schulz Nov 7 '12 at 20:49
    
Thanks! What's a many-one reduction? –  David Faux Nov 7 '12 at 21:09
    
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. –  Pål GD Nov 7 '12 at 21:15
    
@PålGD can you make this an answer? –  Ran G. Jan 12 '13 at 1:21
    
@RanG.Done. Thanks for the reminder. –  Pål GD Jan 12 '13 at 9:29

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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