チューリング還元
Turing reduction
$ \alphaが$ \betaにチューリング還元可能であるとき、$ \alpha\le_T\betaと表記する
定義
自然数の集合$ \alpha,\betaに対して以下が成り立つとき$ \alpha\le_T\betaと書き、$ \alphaが$ \betaにチューリング還元可能である、と言う $ \betaに関する神託機械を使って、$ \alphaの特性関数を計算可能であることを言う 『C言語による計算の理論』.iconp.125では、
$ \alphaの特性関数を計算するプログラムが存在する。
ただし、そのプログラムでは数式中で$ \betaの特性関数を使用してもいいとする。
このとき$ \betaは、$ \alphaに比べて同等以上に難しい
参考