クリーネのT述語

計算可能性理論において、数学者スティーブン・コール・クリーネによって初めて研究されたT述語は、算術の形式理論内で計算可能な関数を表すために使用される特定の自然数の3つのセットです。非公式には、T述語は特定の入力で実行されたときに特定のコンピュータプログラムが停止するかどうかを示し、対応するU関数はプログラムが停止した場合に計算結果を取得するために使用されます。smn定理と同様に_、クリーネによって使用された元の表記法は、この概念の標準用語になっています。[ ^1]

定義は、計算可能な関数（チューリングマシンとして与えられる）に自然数を割り当てる適切なゲーデル番号に依存します。この番号付けは、計算可能な関数のインデックスと関数への入力が与えられた場合に、その入力に対する関数の計算を効果的にシミュレートできるほど十分に効果的でなければなりません。述語は、このシミュレーションを形式化することによって得られます。 ${\displaystyle T}$

三項関係は 3つの自然数を引数として取ります。が入力 で実行されたときにインデックス の計算可能関数の計算履歴をエンコードし、この計算履歴の最後のステップでプログラムが停止する場合、 は真です。つまり、 ${\displaystyle T_{1}(e,i,x)}$${\displaystyle T_{1}(e,i,x)}$${\displaystyle x}$${\displaystyle e}$${\displaystyle i}$

• ${\displaystyle T_{1}}$まず、入力 に対して計算を実行する、インデックス を持つチューリングマシンの完全な構成の有限列のゲーデル数が であるかどうかを尋ねます。${\displaystyle x}$${\displaystyle \langle x_{j}\rangle }$${\displaystyle e}$${\displaystyle i}$
• そうであれば、このシーケンスが計算の開始状態から始まり、シーケンスの各連続要素がチューリング マシンの 1 つのステップに対応するかどうかを尋ねます。${\displaystyle T_{1}}$
• そうであれば、最後に、マシンが停止状態でシーケンスが終了するかどうかを尋ねます。${\displaystyle T_{1}}$${\displaystyle \langle x_{j}\rangle }$

これら 3 つの質問の答えがすべて肯定的であれば、これは真です。そうでない場合は、これは偽です。 ${\displaystyle T_{1}(e,i,x)}$

述語は、述語の入力が与えられたときに、それらの入力に対する述語の真理値を正しく決定する原始再帰関数が存在するという意味で 原始再帰的です。${\displaystyle T_{1}}$

対応するプリミティブ再帰関数があり、が true の場合、入力のインデックスを持つ関数の出力を返します。 ${\displaystyle U}$${\displaystyle T_{1}(e,i,x)}$${\displaystyle U(x)}$${\displaystyle e}$${\displaystyle i}$

クリーネの形式主義では各関数に複数の入力が付加されるため、述語は1つの入力を取る関数にのみ使用できます。複数の入力を取る関数には追加の述語があります。関係 ${\displaystyle T_{1}}$

${\displaystyle T_{k}(e,i_{1},\ldots ,i_{k},x)}$

入力のインデックスを持つ関数の停止計算をエンコードする場合は true です。 ${\displaystyle x}$${\displaystyle e}$${\displaystyle i_{1},\ldots ,i_{k}}$

と同様に、すべての関数は原始再帰的です。このため、すべての原始再帰関数を表現できる算術理論は、およびを表現できます。このような算術理論の例には、ロビンソン算術や、ペアノ算術などのより強力な理論があります。 ${\displaystyle T_{1}}$${\displaystyle T_{k}}$${\displaystyle T}$${\displaystyle U}$

これらの述語は、計算可能関数に対するクリーネの正規形定理（ Soare 1987, p. 15; Kleene 1943, p. 52-53）を得るために使用できる。これは、関数が計算可能であるの は、すべての関数に対して、${\displaystyle T_{k}}$ ${\displaystyle U}$${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$${\displaystyle e}$${\displaystyle n_{1},\ldots ,n_{k}}$

${\displaystyle f(n_{1},\ldots ,n_{k})\simeq U(\mu x\,T_{k}(e,n_{1},\ldots ,n_{k},x))}$、

ここで、μはμ演算子(は が真となる最小の自然数) であり、両辺が未定義であるか、または両辺が定義されていて等しい場合に真となります。定理により、すべての一般再帰関数fの定義は、計算可能関数 とは無関係な最上位 のすぐ下でμ演算子が 1 回だけ使用されるような正規形に書き直すことができます。 ${\displaystyle \mu x\,\phi (x)}$${\displaystyle \phi (x)}$${\displaystyle \simeq}$ ${\displaystyle U}$${\displaystyle f}$

計算可能性を符号化することに加えて、T述語は算術階層における完全な集合を生成するために使用できる。特に、集合

${\displaystyle K=\{e{\mbox{ }}:{\mbox{ }}\exists xT_{1}(e,0,x)\}}$

は停止問題と同じチューリング次数であり、完全な一項関係である（Soare 1987、pp. 28、41）。より一般的には、集合 ${\displaystyle \Sigma _{1}^{0}}$

${\displaystyle K_{n+1}=\{\langle e,a_{1},\ldots ,a_{n}\rangle :\exists xT_{n}(e,a_{1},\ldots ,a_{n},x)\}}$

_は完全な( n +1)項述語である。したがって、算術理論でTn述語の表現が得られれば、そこから完全な述語の表現が得られる。 ${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}^{0}}$

この構成は、ポストの定理のように、算術階層の上位にまで拡張することができる（Hinman 2005、p. 397を参照）。たとえば、集合が完全である場合、集合 ${\displaystyle A\subseteq \mathbb {N} ^{k+1}}$${\displaystyle \Sigma _{n}^{0}}$

${\displaystyle \{\langle a_{1},\ldots ,a_{k}\rangle :\forall x(\langle a_{1},\ldots ,a_{k},x)\in A)\}}$

完了です。 ${\displaystyle \Pi _{n+1}^{0}}$

• ピーター・ヒンマン、2005年、「数学論理の基礎」、 AKピーターズ。ISBN 978-1-56881-262-5 
• Stephen Cole Kleene (1943年1 月)。「再帰述語と量指定子」(PDF)。アメリカ数学会誌。53 (1): 41–73。doi : 10.1090/ S0002-9947-1943-0007371-8。マーティン・デイヴィス編『The Undecidable 』（1965年、255～287ページ）に再録。
• —、1952年、「メタ数学入門」、北ホラント。Ishi pressにより2009年に再版、ISBN 0-923891-57-9。 
• —、1967年。数学論理学、 John Wiley。Doverにより2001年に再版、ISBN 0-486-42533-9。 
• Robert I. Soare、1987年、「再帰的に列挙可能な集合と次数」、Perspectives in Mathematical Logic、Springer。ISBN 0-387-15299-7