Editing Many-one reduction (section)

== Properties ==
* The [[relation (mathematics)|relation]]s of many-one reducibility and 1-reducibility are [[transitive relation|transitive]] and [[reflexive relation|reflexive]] and thus induce a [[preorder]] on the [[powerset]] of the natural numbers.
* <math>A \leq_{\mathrm{m}} B</math> [[if and only if]] <math>\mathbb{N} \setminus A \leq_{\mathrm{m}} \mathbb{N} \setminus B.</math>
* A set is many-one reducible to the [[halting problem]] [[if and only if]] it is [[recursively enumerable]]. This says that with regards to many-one reducibility, the halting problem is the most complicated of all recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem.
* The specialized halting problem for an ''individual'' Turing machine ''T'' (i.e., the set of inputs for which ''T'' eventually halts) is many-one complete iff ''T'' is a [[universal Turing machine]].  Emil Post showed that there exist recursively enumerable sets that are neither [[Decidability (logic)|decidable]] nor m-complete, and hence that ''there exist <u>non</u>universal Turing machines whose individual halting problems are nevertheless undecidable''.