313
правок
Изменения
→Рекурсивные функции
<tex>\mathbb{N} \rightarrow \mathbb{N}</tex>, <tex>\mathrm{Z}(x) = 0</tex>
<li> <tex>\mathrm{N}</tex>{{---}} функция следования. </li>
<tex>\mathbb{N} \rightarrow \mathbb{N}</tex>, <tex>\mathrm{N}(x) = x'</tex>, где <tex>x' = x + 1</tex>.
<li> Проекция<tex>\mathrm{U^n_i}</tex> {{---}} проекция.</li>
<tex>\mathrm{U^n_i}: \mathbb{N}^{n} \rightarrow \mathbb{N}</tex>, <tex>\mathrm{U^n_i} (x_1, ... x_n) = x_i</tex>
<li> Подстановка<tex>S</tex>{{---}} подстановка.</li>
Если <tex>\mathrm{f}: \mathbb{N}^{n} \rightarrow \mathbb{N}</tex> и <tex>\mathrm{g_1}, ... \mathrm{g_n}: \mathbb{N}^{m} \rightarrow \mathbb{N}</tex>, то <tex>\mathrm{S}\langle{}\mathrm{f},\mathrm{g_1},...\mathrm{g_n}\rangle: \mathbb{N}^{m} \rightarrow \mathbb{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>
<li> Примитивная <tex>R</tex> {{---}} примитивная рекурсия.</li>
Если <tex>\mathrm{f}: \mathbb{N}^{n} \rightarrow \mathbb{N}</tex> и <tex>\mathrm{g}:\mathbb{N}^{n+2} \rightarrow \mathbb{N}</tex>, то <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle: \mathbb{N}^{n+1} \rightarrow \mathbb{N}</tex>, при этом <tex>\mathrm{R}\langle{}\mathrm{f},\mathrm{g}\rangle (x_1,...x_n,y) = \left\{\begin{array}{ll}
\end{array}\right.</tex>
<li> Минимизация<tex>\mu</tex> {{---}} минимизация.</li>
Если <tex>\mathrm{f}: \mathbb{N}^{n+1} \rightarrow \mathbb{N}</tex>, то <tex>\mu \langle{}\mathrm{f}\rangle: \mathbb{N}^{n} \rightarrow \mathbb{N}</tex>, при этом <tex>\mu \langle{}\mathrm{f}\rangle (x_1,...x_n)</tex> — такое минимальное число <tex>y</tex>, что <tex>\mathrm{f}(x_1,...x_n,y) = 0</tex>. Если такого <tex>y</tex> нет, результат данного примитива неопределен.
