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

Опера́ція найме́ншого рі́вня — операція, що зіставляє кожній рекурсивній функції від $n$ змінних $g(x_1,...,x_n)$ рекурсивну функцію $f(x_1,...,x_{n-1})=\mu x_{n}g\times (x_1,\dots ,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(a_1,...,a_n)$ вважається невизначеною при даних фіксованих значеннях.

Література

• Шаблон:ЕК