くだらねぇ問題はここへ書け (836レス)
上下前次1-新
抽出解除 必死チェッカー(本家) (べ) レス栞 あぼーん
580: 2022/08/29(月)12:18 ID:cg/tjCFi(1/3) AAS
関数は自然数上の関数だけを考えます。
【定義(recursion)】
Aが1変数関数で、Bが3変数関数、Sが後者関数のとき、以下の2つの式で新しい2変数関数Fを定義できる。
F(x, 0) = A(x)
F(x, S(n)) = B(x, n, F(x, n))
このとき、関数Aと関数Bからrecursionによって関数Fを得るという。
【定義(iteration)】
Aが1変数関数で、Bが2変数関数、Sが後者関数のとき、以下の2つの式で新しい2変数関数Fを定義できる。
F(x, 0) = A(x)
F(x, S(n)) = B(n, F(x, n))
省5
581: 2022/08/29(月)12:19 ID:cg/tjCFi(2/3) AAS
【定理】
A, B, I, J, K, Lをそれぞれ1, 3, 1, 2, 1, 1変数関数として、特にI(x)=x, K(J(x, y))=x, L(J(x, y))=yを満たすとする。
2変数関数FがA, Bからrecursionによって定義されているとき
FはA, B, I, J, K, Lから合成とiteration を有限回適用して定義できる。
(証明)
前提より、次の2式でFが定義されている。
F (x, 0) =A(x)
F (x, S (n)) =B(x, n, F(x, y, n))
いまから
F (x, n) = F’ (x, n)を満たすF’ をA, B, I, J, K, Lから合成とiterationによって定義する。
省16
582(1): 2022/08/29(月)12:20 ID:cg/tjCFi(3/3) AAS
これはRaphael M. Robinsonの “Primitive recursive functions.” (Bull. Amer. Math. Soc. October. 1947: 925 – 942.)に書いてあります。
たしかに証明でやっているようにα、βを定義して、それらからiterationでGを定義すれば、Gは都合のいい性質を満たしてくれていて、Gから簡単に目的のF’を定義できます。
しかし、証明を追うことはできても発想を理解できなくて釈然としません。
とくにG(x, y)=J(x, F(x, y))を満たすGを得るためにA, BとI, J, K, Lからあのようにα, βを定義するに至った気持ちがわかりません。
上下前次1-新書関写板覧索設栞歴
スレ情報 赤レス抽出 画像レス抽出 歴の未読スレ AAサムネイル
ぬこの手 ぬこTOP 1.390s*