当前位置：文江博客话题详情

如何证明加法是原始递归？

发布于 2024-12-04 07:55:48 字数 76 浏览 2 评论 0原文

我如何在数字示例中表明加法是原始递归的。

我通过证明理解了为什么它是原始递归的，但我只是无法想象它如何与数字进行原始递归。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浪漫人生路 2024-12-11 07:55:48

为了证明函数 φ 是原始递归函数，只需提供原始递归函数的有限序列，以常量、后继函数和投影函数开始，并以 φ 结束，这样每个函数都是通过组合和原始递归从先前的函数构造的。定义原始递归加法函数

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

，其中 P[m/n] 是返回其 n 个参数的 m 投影函数。 >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]

函数 φ由原始递归函数的公理提供。函数ψ由步骤(4)中的原始递归函数S和P[3/3]组合而成。最后，由步骤(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]

不清楚你到底在问什么，所以我给出了加法的原始递归定义的一般概述，加法是原始递归的证明，并提供了一个示例计算。如果您仍然不清楚，对原始递归函数的小值执行计算可能会有所帮助。

To show that a function φ is primitive recursive, it suffices to provide a finite sequence of primitive recursive functions beginning with the constant, successor and projection functions and terminating with φ such that each function is constructed from prior functions by composition and primitive recursion. The primitive recursive addition function is defined

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

where P[m/n] is the m-ary projection function returning its nth argument for n >= 1 and n <= m. To demonstrate that add is primitive recursive, we must construct φ and ψ from the basic functions:

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]

The function φ is provided by the axioms of primitive recursive functions. The function ψ is constructed by composition from the primitive recursive functions S and P[3/3] in step (4). Finally, the function add is constructed from φ and ψ in step (6) by primitive recursion. To see how a value is computed by a primitive recursive function such as add, it suffices to systematically substitute the right-hand sides of function definitions where appropriate, then simplify. I've collapsed substitution and simplification of composition in the following example:

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]

It's unclear precisely what you're asking, so I gave a general overview of the primitive recursive definition of addition, the proof that addition is primitive recursive, and provided an example computation. If you're still unclear, it might be helpful to perform computations on small values of primitive recursive functions.

回复收藏 0 原文

~没有更多了~