Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction.  I would like to know the steps and conventions for writing a many-one reduction proof.  This answer was somewhat helpful, but like other explanations I've heard, it sounds too similar to a proof by contradiction for me to understand the difference.My specific points of confusion:The exact meaning of $A \leq _{m} B$Do we reduce an unknown problem to a known problem, or the oppositeDoes the reduction function transform a known problem into an unknown problem, or the oppositeHow a many-one reduction is different from a proof by contradiction.  It seems like a simpler version of the same logic; if so, how is the simplification justifiedI am only interested in many-one reductions of language/Turing machine problems (in case the term has meaning in other contexts as well).  Any help is appreciated, including links and illustrative examples.  Thanks.
How to write a many-one reduction proof
turing machines;reductions
A many-one reduction is not a proof-by-contradiction per se, it is an application of a theorem. The theorem is:Let $L,L'\subseteq \{0,1\}^*$, and $L \leq_m L'$. Then, it holds thatIf $L$ is undecidable, then $L'$ is undecidable.if $L'$ is decidable, then $L$ is decidable.I will omit the proof, there are plenty of resources where you can read up on it. You can view the statement $L \leq_m L'$ intuitively as The language $L$ is easier to decide than the language $L'$. And that's what a reduction proof does. You show that one language (the hard, known one, like the halting problem $H_0$)  is easier to decide than a new, unknown language $L$. By showing $H_0 \leq_m L$ you've essentially shown (by application of the above theorem) that the halting problem is easier than $L$. Thus, $L$ cannot be decided.So, to answer your questions:$A \leq_m B$ means that the language $A$ is easier to decide than the language $B$.To show hardness, you reduce YOUR_HARD_LANGUAGE $\leq_m$ SOME_NEW_LANGUAGE. To show computability, you can reduce in the other direction, but usually it's simpler to just construct a TM that solves the given problem.A reduction $L \leq_m L'$ takes an instance $x \in \{ 0,1\}^*$ and does the following with it: If $x \in L$, you make sure that the reduction $f(x) \in L'$. If $x \not \in L$, then the reduction maps $f(x) \not \in L'$. So - if you prove hardness, you transform a known hard problem into the unknown problem.It is a contradiction in the sense of If I could solve the new problem, then I can solve the hard problem, which cannot be, since it is proven to be hard. This contradiction is hidden in the Theorem above and you just slap it (implicitly) on every reduction you do.I hope that helped. As I said, my main intuitive approach to reductions is How could I use a new language $L'$ to solve an old, hard language $L$?.