Изменения

Перейти к: навигация, поиск

Примитивно рекурсивные функции

4 байта добавлено, 16:13, 6 ноября 2016
Рекурсивные функции
# <tex>\mathrm{N}: \mathbb{N} \rightarrow \mathbb{N}</tex>, <tex>\mathrm{N}(x) = x'</tex>
# Проекция. <tex>\mathrm{U^n_i}: \mathbb{N}^{n} \rightarrow \mathbb{N}</tex>, <tex>\mathrm{U^n_i} (x_1, ... x_n) = x_i</tex>
# Подстановка. Если <tex>\mathrm{f}: \mathrmmathbb{N}^{n} \rightarrow \mathrmmathbb{N}</tex> и <tex>\mathrm{g_1}, ... \mathrm{g_n}: \mathrmmathbb{N}^{m} \rightarrow \mathrmmathbb{N}</tex>, то <tex>\mathrm{S}\langle{}\mathrm{f},\mathrm{g_1},...\mathrm{g_n}\rangle: \mathrm{N^m} \rightarrow \mathrm{N}</tex>. При этом <tex>\mathrm{S}\langle{}\mathrm{f},\mathrm{g_1},...\mathrm{g_n}\rangle (x_1,...x_m) = \mathrm{f}(\mathrm{g_1}(x_1,...x_m), ... \mathrm{g_n}(x_1,...x_m))</tex>
# Примитивная рекурсия. Если <tex>\mathrm{f}: \mathrm{N^n} \rightarrow \mathrm{N}</tex> и <tex>\mathrm{g}: \mathrm{N^{n+2}} \rightarrow \mathrm{N}</tex>, то <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle: \mathrm{N^{n+1}} \rightarrow \mathrm{N}</tex>, при этом <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle (x_1,...x_n,y) = \left\{\begin{array}{ll}
\mathrm{f}(x_1,...x_n) & , y = 0\\
313
правок

Навигация