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

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

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

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

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

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

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

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

Посилання

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