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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії рекурсії, операція мінімізації, або μ-оператор - це рекурсивний оператор, який при застосуванні до певної обчислюваної функції 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(x1,x2,...,xn,y)) дорівнює найменшому значенню y такому що g(x1,x2,...,xn,y)=0.

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

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


Посилання[ред.ред. код]

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