Minimalizzazione

Da Wikipedia, l'enciclopedia libera.

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

Definizione[modifica | modifica sorgente]

Supponiamo che R( y, x1 , . . ., xk ) 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 limtato "µyy<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 y R(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[modifica | modifica sorgente]

  • 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.