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₁ , . . ., 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.

Bibliografia

• Stephen Kleene (1952) Introduction to Metamathematics, North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint).
• Marvin L. Minsky (1967), Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, N.J.

On pages 210-215 Minsky shows how to create the μ-operator using the register machine model, thus demonstrating its equivalence to the general recursive functions.

• George Boolos, John Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, UK. Cf pp. 70-71.