Операція найменшого рівня

Опера́ція найме́ншого рі́вня — операція, що зіставляє кожній рекурсивній функції від $\!n$ змінних $\!g(x_{1},...,x_{n})$ рекурсивну функцію $\!f(x_{1},...,x_{n-1})=\mu x_{n}g\times (x_{1},\ldots ,x_{n})$ від $\!n-1$ змінної.

Значення $\!f(x_{1},...,x_{n-1})$ дорівнює такому найменшому числу

$\!k$, що $\!g(x_{1},...,x_{n-1},k)=0$ і для всіх $\!z<k$ функція $\!f(x_{1},...,x_{n-1},z)$ визначена і не дорівнює нулю.

Якщо для деяких фіксованих значень $\!a_{1},...,a_{n}$ такого $\!k$ не існує, то $\!f\quad (a_{1},...,a_{n})$ вважається невизначеною при даних фіксованих значеннях.

Література

• Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.