1

足し算がプリミティブ再帰的であることを数字の例で示すにはどうすればよいですか。

証明を通してプリミティブ再帰的である理由は理解できますが、数字でプリミティブ再帰的にどのように機能するか想像できません。

4

1 に答える 1

5

関数φが原始再帰的であることを示すには、定数関数、後継関数、射影関数で始まり、φ合成と原始再帰によって前の関数から各関数が構築されるように終了する、原始再帰関数の有限シーケンスを提供するだけで十分です。プリミティブ再帰加算関数が定義されています

add(0,x)     = φ(x)
add(n + 1,x) = ψ(n,x,add(n,x))
  where φ = P[1/1]
        ψ = S ∘ P[3/3]

ここP[m/n]で、 はおよびのth 引数をm返す -ary 射影関数です。これがプリミティブ再帰であることを示すには、基本関数からandを作成する必要があります。nn >= 1n <= maddφψ

1. P[1/1]                [Axiom]
2. P[3/3]                [Axiom]
3. S                     [Axiom]
4. S ∘ P[3/3]            [1,3 Composition]
6. PR(P[1/1],S ∘ P[3/3]) [1,4 Primitive Recursion]

この関数φは、原始再帰関数の公理によって提供されます。関数ψは、基本的な再帰関数からの構成によって、SおよびP[3/3]ステップ (4) で構築されます。最後に、関数はステップ (6) から原始再帰によってadd構築されφます。ψなどのプリミティブな再帰関数によって値がどのように計算されるかを確認するにはadd、関数定義の右辺を適切な場所で体系的に置き換えてから単純化するだけで十分です。次の例では、構成の置換と単純化を折りたたんでいます。

add(2,3) = S(P[3/3](1,3,add(1,3)))                 [Def. ψ]
         = S(P[3/3](1,3,S(P[3/3](0,3,add(0,3)))))  [Def. ψ]
         = S(P[3/3](1,3,S(P[3/3](0,3,P[1/1](3))))) [Def. φ]
         = S(P[3/3](1,3,S(P[3/3](0,3,3))))         [Def. P[1/1]]
         = S(P[3/3](1,3,S(3)))                     [Def. P[3/3]]
         = S(P[3/3](1,3,4))                        [Def. S]
         = S(4)                                    [Def. P[3/3]]
         = 5                                       [Def. S]

あなたが何を求めているのか正確には不明なので、加算のプリミティブ再帰的定義の一般的な概要、加算がプリミティブ再帰的であることの証明、および計算例を提供しました。それでも不明な場合は、プリミティブ再帰関数の小さな値で計算を実行すると役立つ場合があります。

于 2011-09-30T16:10:19.173 に答える