還元 (計算複雑性理論)
ある言語が決定不可能であることを停止問題からの還元で示す例を以下で示す。チューリングマシン M が(受容するしないに関わらず)入力文字列wについて停止するかどうかという問題を H(M, w) と表記する。この言語は決定不可能であることが知られている。チューリングマシンMの受容する文字列がないかどうかという決定問題を E(M) と表記する。E が決定不可能であることを H からの還元によって示す。
矛盾を導くため、E の判定器Rを想定する。これを使って(存在しないと分かっている)Hの判定器Sを作る。Mとw(チューリングマシンと入力文字列)を入力したときのS(M, w)の動作を以下のように定義する。S は、Mがwを入力したときに停止する場合だけ、wのみを受容するチューリングマシンNを生成するものとする(停止しない場合、空の言語を受容するNを作る)。すると、判定器 S は R(N) を評価してNの受容する言語が空であるかどうかを判定できる。RがNを受容するなら、Nの受容する言語は空であり、Mが入力wで停止しないから、Sはそのように判定できる。RがNを受容しないならNの受容する言語は空ではなく、Mは入力wで停止するので、Sはそのように判定する。従って、Eの判定器Rがあれば、任意のマシンMと入力wに関する停止問題H(M, w)の判定器Sを作ることができる。そのようなSは存在しないことが既知であるため、言語Eも決定不可能であることが導かれる。