Cook還元とも言う

還元可能性の還元の方法の一つ

\alphaが\betaにチューリング還元可能であるとき、\alpha\le_T\betaと表記する

定義

自然数の集合\alpha,\betaに対して以下が成り立つとき\alpha\le_T\betaと書き、\alphaが\betaにチューリング還元可能である、と言う

\betaに関する神託機械を使って、\alphaの特性関数を計算可能であることを言う

p.125では、

\alphaの特性関数を計算するプログラムが存在する。

ただし、そのプログラムでは数式中で\betaの特性関数を使用してもいいとする。

このとき\betaは、\alphaに比べて同等以上に難しい

\alpha\equiv_T\betaのことはチューリング同値と呼ぶ

参考

『C言語による計算の理論』 p.125