gotchaMinor
Why does $A_\text{TM} \le_m \text{HALTING} \le_m \text{HALTING}^\varepsilon$?
Viewed 0 times
whyle_mtexthaltingdoesvarepsilon
Problem
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?
$$
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?
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#6541, answer score: 3
Revisions (0)
No revisions yet.