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

Опера́ція найме́ншого ко́реня — операція, що зіставляє кожній рекурсивній функції від 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, с. 129.

Див. також

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