正規形定理
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/08 15:15 UTC 版)
クリーネの正規形定理（英語: Kleene's_T_predicate#Normal_form_theorem）は、次を主張する: 原始再帰関数 U ( y ) {\displaystyle U(y)\!} と T ( y , e , x 1 , … , x k ) {\displaystyle T(y,e,x_{1},\ldots ,x_{k})\!} について、k 個の自由変数を持つμ再帰関数 f ( x 1 , … , x k ) {\displaystyle f(x_{1},\ldots ,x_{k})\!} があり、以下を満足する e が存在する。 f ( x 1 , … , x k ) ≃ U ( μ y T ( y , e , x 1 , … , x k ) ) {\displaystyle f(x_{1},\ldots ,x_{k})\simeq U(\mu y\,T(y,e,x_{1},\ldots ,x_{k}))} . ここで、e は関数 f のインデックスまたはゲーデル数である。つまり、任意のμ再帰関数は原始再帰関数に1回だけμ作用素を適用することで定義される。 ミンスキー（1967）は、ここで定義された U が基本的に万能チューリングマシンと等価であると述べた。
※この「正規形定理」の解説は、「μ再帰関数」の解説の一部です。
「正規形定理」を含む「μ再帰関数」の記事については、「μ再帰関数」の概要を参照ください。
ウィキペディア小見出し辞書の「正規形定理」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 正規形定理のページへのリンク
