minimalizzazione

Particolare tipo di procedimento, usato in logica matematica e soprattutto nella teoria della ricorsività, nel quale si fa uso dell’operatore di m., o operatore-μ, che consente di definire in modo opportuno una funzione a partire da una funzione data o da un predicato dato. Procedimento e operatore di m. possono essere intuitivamente descritti mediante la formula μxPx che si legge «il più piccolo x tale che risulti vero l’enunciato Px». In generale, per definire una funzione (x₁, ..., x_n) a partire da una funzione nota g(x₁, ..., x_n, y), per m. di y, si usa la formula:

f(x₁, ..., x_n) = μy[g(x₁, ..., x_n, y) = 0]

che si legge: «f(x₁, ..., x_n) è uguale al più piccolo y tale che sia g(x₁, ..., x_n, y)=0». Se, invece, si parte da un predicato noto Px₁ ... x_n y, la formula è:

f(x₁, ..., x_n) = μyPx₁ ... x_n y.

Qualora in una delle due definizioni si supponga che questo valore minimo esista sempre, la m. si dice normale. Se si suppone che questo valore minimo debba, in ogni caso, essere minore di un valore z dipendente da x₁, ..., x_n, la m. si dice limitata.