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

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

Словом оператор позначається функція $\Phi :\,{\mathcal {F}}_{m}\to {\mathcal {F}}_{n}$. (Тут оператори позначатимуться великими грецькими: $\Phi ,\,\Psi ,\,\ldots$)

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

$\Phi :\,{\mathcal {F}}_{m}\to {\mathcal {F}}_{n}$ — рекурсивний оператор, якщо існує обчислювана функція $\phi (z,\mathbf {x} )$, така що

$\forall f\in {\mathcal {F}}_{m},\,x\in \mathbb {N} ^{n},\,y\in \mathbb {N}$

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

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

Посилання

1. Nigel Cutland. Computability, an introduction to recursive function theory. — Cambridge University Press. — С. 251. — ISBN 0521294657, 9780521294652.