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

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

Значення $f(x_{1},\dots ,x_{n-1})$ дорівнює такому найменшому числу k, що $g(x_{1},\dots ,x_{n-1},k)=0$ і для всіх z < k функція $f(x_{1},\dots ,x_{n-1},z)$ визначена і не дорівнює нулю. Якщо для деякого фіксованого значення $a_{1},\dots ,a_{n-1}$ такого k не існує, то $f(a_{1},\dots ,a_{n-1})$ вважається невизначеною при заданих фіксованих значеннях.

Джерела інформації

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

Див. також

• Функції рекурсивні
• Теорія алгоритмів
• Рекурсія