Minimalizzazione
# Minimalizzazione

Nella teoria della computabilità, l'operatore μ, operatore di minimalizzazione, o operatore di ricerca illimitata ricerca i minimi numeri naturali di una proprietà data.

## Definizione

Supponiamo che R( y, $x_1$ , . . ., $x_k$ ) sia una relazione k+1-aria fissata sui numeri naturali. L'operatore mu "μy", in una delle forme illimitata o limitata, è una "funzione teoretica di numero" definita dai numeri naturali { 0, 1, 2, . . . } ai numeri naturali. Comunque, "μy" contiene un predicato sui numeri naturali che restituisce il valore vero quando il predicato è soddisfatto e falso quando non lo è.

L'operatore mu limitato apparve per la prima volta nel Chapter IX Primitive Recursive Functions, §45 Predicates, prime factor representation di Kleene (1952), as:

    "$\mu y_{y<z}R(y).\ \ {\mbox{Il minimo}}\ y<z\ {\mbox{tale che}}\ R(y),\ {\mbox{se}}\ (\exists y)_{y<z}R(y);\ {\mbox{altrimenti}},\ z.$" (p. 255)

Kleene evidenzia che qualsiasi delle 6 limitazioni di diseguaglianza sull'intervallo della variabile y è permessa, esempio: "y < z", "y = z", "w < y < z", "w < y = z", "w = y < z", "w = y = z". "Quando l'intervallo indicato non contiene y tale che R(y) [è "vera"], il valore dell'espressione "μy" è il numero cardinale dell'intervallo"(p. 226); questo è dato dal fatto che il default "z" appare nella definizione di sopra. Come mostrato sotto, l'operatore mu limitato $"μy_{y<z}"$ è definito in termini di due funzioni ricorsive primitive chiamate la somma finita Σ e il prodotto finito Π, una funzione predicato che "effettua la prova" e una funzione che converte { t, f } in { 0, 1 }.

Nel capitolo XI 57 delle funzioni ricorsive generali, Kleene definisce l'operatore μ illimatato circa la variabile y nel seguente modo:

    "$(\exists y)\mu yR(y)=\{{\mbox{il minore (numero naturale)}}\ y\ {\mbox{tale che}}\ R(y)\}$" (p. 279, dove "$(\exists y)$" significa che "Esiste una y tale che..."

In questo caso la nuova funzione restituisce y quando un y esiste e verifica il predicato R, è indefinita altrimenti. L'operatore di minimalizzazione, unitamente a quello di ricorsione e composizione, forma un insieme di operatori sufficienti alla creazione di funzioni ricorsive totali.

