Рекурсивний оператор

Нехай ${ℱ}_n,(n\ge 0)$ — клас всіх часткових функцій з ${\mathbb{N}}^n$ в $\mathbb{N}$.

Словом оператор позначається функція $\mathrm{\Phi }:{ℱ}_m\to {ℱ}_n$. (Тут оператори позначатимуться великими грецькими: $\mathrm{\Phi },\mathrm{\Psi },\dots$)

Тут будемо розглядати лише тотальні оператори, тобто такі для яких область визначення збігається з ${ℱ}_m$.

$\mathrm{\Phi }:{ℱ}_m\to {ℱ}_n$ — рекурсивний оператор, якщо існує обчислювана функція $\varphi (z,𝐱)$, така що

$\mathrm{\forall }f\in {ℱ}_m,x\in {\mathbb{N}}^n,y\in \mathbb{N}$

$\mathrm{\Phi }(f)(𝐱)\simeq y$ тоді і тільки тоді, коли існує скінченне $\theta \subseteq f$, таке що $\varphi (\tilde{\theta },𝐱)\simeq y$.

Зауважте, що $\varphi$ не обов'язково тотальна.

Посилання

1. Шаблон:Книга