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

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

Для функції

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

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

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

${\displaystyle f(z)=0}$ і: для всіх ${\displaystyle y<z}$, ${\displaystyle f(y)}$ визначена та ${\displaystyle 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.