Как показать, что сложение является примитивно-рекурсивным? - PullRequest
Новая
       22

Как показать, что сложение является примитивно-рекурсивным?

1 голос
/ 14 сентября 2011

Как мне показать в примере с числами, что сложение является примитивно-рекурсивным.

Я понимаю, почему оно является примитивно-рекурсивным в доказательстве, но я просто не представляю, как оно работает примитивно-рекурсивно с числами.

1 Ответ

3 голосов
/ 30 сентября 2011

Чтобы показать, что функция φ является примитивно-рекурсивной, достаточно предоставить конечную последовательность примитивно-рекурсивных функций, начинающуюся с функций константы, преемника и проекции и заканчивающуюся φ, так что каждая функция создается из предыдущих функцийпо композиции и примитивной рекурсии.Примитивно-рекурсивная функция сложения определена 

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 -арная проекционная функция, возвращающая свой n -й аргумент для 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).Наконец, функция add строится из φ и ψ на шаге (6) с помощью примитивной рекурсии.Чтобы увидеть, как значение вычисляется примитивной рекурсивной функцией, такой как 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]

Непонятно, о чем именно вы спрашиваете, поэтому я дал общий обзор примитивно-рекурсивного определения сложения, доказательство того, что сложениеявляется примитивно рекурсивным, и предоставил пример вычисления.Если вам все еще неясно, может быть полезно выполнить вычисления для небольших значений примитивных рекурсивных функций.

...