チューリング同値
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:45 UTC 版)
「チューリング次数」の記事における「チューリング同値」の解説
詳細は「チューリング還元」を参照 この記事では以後「集合」と言えば「自然数の集合」を指すこととする。ある数が集合 X {\displaystyle X} の元かどうかを、オラクル集合 Y {\displaystyle Y} を持つ神託機械を用いて決定できるとき、 X {\displaystyle X} は Y {\displaystyle Y} にチューリング還元可能であると言い、 X ≤ T Y {\displaystyle X\leq _{T}Y} と書く。 二つの集合 X {\displaystyle X} と Y {\displaystyle Y} について、 X {\displaystyle X} が Y {\displaystyle Y} にチューリング還元可能であり、かつ、 Y {\displaystyle Y} が X {\displaystyle X} にチューリング還元可能であるとき、これらの集合は チューリング同値 であると言い、 X ≡ T Y {\displaystyle X\equiv _{T}Y} と書く。 ≡ T {\displaystyle \equiv _{T}} という関係は同値関係と捉えることができる。すなわち任意の集合 X {\displaystyle X} 、 Y {\displaystyle Y} 、 Z {\displaystyle Z} について X ≡ T X {\displaystyle X\equiv _{T}X} X ≡ T Y {\displaystyle X\equiv _{T}Y} ならば Y ≡ T X {\displaystyle Y\equiv _{T}X} もし X ≡ T Y {\displaystyle X\equiv _{T}Y} かつ Y ≡ T Z {\displaystyle Y\equiv _{T}Z} ならば、 X ≡ T Z {\displaystyle X\equiv _{T}Z} 。
※この「チューリング同値」の解説は、「チューリング次数」の解説の一部です。
「チューリング同値」を含む「チューリング次数」の記事については、「チューリング次数」の概要を参照ください。
- チューリング同値のページへのリンク
