Операція мінімізації

В теорії рекурсії, операція мінімізації, або μ-оператор - це рекурсивний оператор, який при застосуванні до певної обчислюваної функції f, дає обчилювану функцію яка при суперпозиції себе в f дає нуль.

Для функції

$f:\mathbb{N}\rightarrow\mathbb{Z}$,

$\mu y\left[f(y)=0\right]=z$

тоді і тільки тоді

$f(z)=0$ і

для всіх $y<z$, $f(y)$ визначена та $f(y)>0$.

Інші варіанти означень

M(g(x₁,x₂,...,x_n,y)) дорівнює найменшому значенню y такому що g(x₁,x₂,...,x_n,y)=0.

Або, якщо сформулювати інакше, то M ставить у відповідність (n+1)-арній функції g, n-арну функцію f, яку позначають M(g), що задається так:

Для всіх y від 0 до нескінченності обчислюємо значення g(x₁,x₂,...,x_n,y). Для першого y такого що g(x₁,x₂,...,x_n,y)=0 присвоюємо f(x₁,x₂,...,x_n)=y.

Посилання

1. Використано матеріали статті вікіпедії мовою есперанто.
2. CybWiki