多対一還元
多対一還元や一対一還元は推移的かつ反射的であり、従って自然数の冪集合の上で半順序を成す。
A ≤ m B {\displaystyle A\leq _{m}B} の必要十分条件は N ∖ A ≤ m N ∖ B {\displaystyle \mathbb {N} \setminus A\leq _{m}\mathbb {N} \setminus B} である。
ある集合が停止問題に多対一還元可能となる必要十分条件は、それが帰納的可算集合であることである。これは多対一還元に関する限り、あらゆる帰納的可算集合の中で停止問題が最も複雑であることを意味する。従って停止問題は多対一完全。
個別のチューリングマシン T に特化した停止問題(即ち、T が最終的に停止するような入力の集合)が多対一完全である必要十分条件は T が万能チューリングマシンであることである。エミール・ポストは決定可能でもm-完全でもない帰納的可算集合が存在することを示した。従って固有の停止問題が決定不可能であるような万能でないチューリングマシンが存在する。(c.f. 単純集合)