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

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

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

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

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

Ця стаття потребує істотної переробки. Можливо, її необхідно доповнити, переписати або вікіфікувати. Пояснення причин та обговорення — на сторінці Вікіпедія: Статті, що необхідно поліпшити. Тому, хто додав шаблон: зважте на те, щоб повідомити основних авторів статті про необхідність поліпшення, додавши до їхньої сторінки обговорення такий текст: {{subst:поліпшити автору|Операція мінімізації|10 лютого 2025}} ~~~~, а також не забудьте описати причину номінації на підсторінці Вікіпедія:Статті, що необхідно поліпшити за відповідний день. (10 лютого 2025)

У теорії рекурсії, операція мінімізації, або μ-оператор — це рекурсивний оператор, який при застосуванні до певної обчислюваної функції 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.

1. ↑ Klenee, 1952, с. 225, Chapter IX Primitive Recursive Functions, §45 Predicates, prime factor representation.

• Kleene, Stephen Cole (1952). Introduction to metamathematics. New York Tokyo: Ishi Press. ISBN 9780923891572.