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]是m-ary 投影函数返回其nth 参数n >= 1和n <= m。为了证明这add是原始递归，我们必须从基本函数构造φ和：ψ

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 回答