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

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

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

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

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

Література

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