Користувач:Галактион/Операція примітивної рекурсії

Подстраница "Користувач:Галактион/Операція примітивної рекурсії" создана для того, чтобы перенести информацию из раздела "Обговорення" статьи "Операція примітивної рекурсії". Галактион 19:33, 5 березня 2010 (UTC)

Примечание к статье "Операция примитивной рекурсии"

F(0, x₁,..., x_m) = G(x₁,..., x_m) $~\land$ F(1, x₁, ..., x_m) = H(0, F(0, x₁,..., x_m), x₁,..., x_m) $~\land$ F(2, x₁,..., x_m) = H(1, F(1, x₁,..., x_m), x₁,..., x_m) $~\land$ ... $~\Leftrightarrow$

F(0, x₁, ... , x_m) = G(x₁, ..., x_m) $~\land \forall$n (n $~\in$ N \ {0} $~\to$ F(n, x₁, ... , x_m) = H(n − 1, F(n - 1, x₁, ... , x_m), x₁, ... , x_m) ),

где:

F : N^m+1 $~\mapsto$ N – [искомая] натуральная функция m + 1 натуральных аргументов,

G : N^m $~\mapsto$ N – [известная] натуральная функция m натуральных аргументов,

H : N^m+2 $~\mapsto$ N – [заданная] натуральная функция m + 2 натуральных аргументов.

Простейшая "операция примитивной рекурсии" имеет вид:

F(0) = G $~\land \forall$n (n $~\in$ N \ {0} $~\to$ F(n) = H(n − 1, F(n − 1)) ),

где:

F : N $~\mapsto$ N – [искомая] натуральная функция одного натурального аргумента,

G – [известная] постоянная (функция нуля аргументов), а именно натуральное число,

H : N² $~\mapsto$ N – [заданная] натуральная функция двух натуральных аргументов

Простейшую "операцию примитивной рекурсии" можно записать в "индексной форме":

F₀ = G $~\land \forall _{n\ \in \ \mathbb {N} \setminus \{0\}}$ (i = n − 1 $~\land$ j = F_{n − 1} $\to$ F_n = H_{i, j})

Пример 1 (простейшей "операции примитивной рекурксии")

F(0) = 1 $~\land \forall$n ( n $\in$ N \ {0} $~\to$ F(n) = (n − 1 + 1) • F(n − 1) )

или в других обозначениях

F₀ = 1 $~\land \forall _{n\ \in \ \mathbb {N} \setminus \{0\}}$ (i = n − 1 $~\land$ j = F_{n − 1} $~\to$ F_n = (i + 1) • j)

Примечания

1. В этом примере G = 1 $~\land$ H(n − 1, F(n − 1)) = (n − 1 + 1) • F(n − 1)) = n • F(n − 1)

2 Обратите внимание, что F(0) = 1 $~\land \forall$n (n $~\in$ N \ {0} $~\to$ F(n) = n • F(n − 1) ) $~\Leftrightarrow \forall$n (n $~\in$ N $~\to$ F(n) = n!)

Пример 2 (простейшей "операции примитивной рекурсии")

F(0) = 1 $~\land \forall$n (n $~\in$ N \ {0} $~\to$ F(n) = (n − 1 + 1) + f(n − 1) )

или в других обозначениях

F₀ = 1 $~\land \forall _{n\ \in \ \mathbb {N} \setminus \{0\}}$ (i = n − 1 $~\land$ j = F_n−1 $~\to$ F_n = 1 + i + j)

Примечание

1. В этом примере G = 1 $~\land$ H(n − 1, F(n − 1)) = (n − 1 + 1) + F(n − 1) = n + F(n − 1)

2. Обратите внимание, что F(0) = 1 $~\land \forall$n (n $~\in$ N \ {0} $~\to$ F(n) = n + f(n - 1) ) $~\Leftrightarrow \forall$n (n $~\in$ N $~\to$ F(n) = n • (n + 1) / 2 )

Галактион 00:11, 9 серпня 2009 (UTC)