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

У теорії рекурсії, операція мінімізації (Шаблон:Lang-en), або μ-оператор  (Шаблон:Lang-en) знаходить найменше натуральне число з заданою властивістю. Додавання операції мінімізації до примітивно рекурсивних функцій дозволяє визначити всі обчислювані функції.

Визначення

Нехай R(y, x₁, ..., x_k) це (k+1)-арне відношення на множині натуральних чисел. μ-оператор "μy", у як обмеженій так і не обмеженій формі, це a "теоретико-числова функція" визначена з натуральних чисел в натуральні числа. Щоправда, "μy" містить предикат над натуральними числами.

Обмежений μ-оператор визначається КлініШаблон:Sfn як:

"$\mu y_{y<z}R(y).\text{Найменше}y<z\text{таке що}R(y),\text{якщо}(\mathrm{\exists }y{)}_{y<z}R(y);\text{інакше},z.$"

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

Для функції

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

$\mu y[f(y)=0]=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.

Література

• Шаблон:Cite book