minimalizzazione, operatore di
minimalizzazione, operatore di
minimalizzazione, operatore di o schema della minimalizzazione, una delle regole attraverso le quali si costruiscono le funzioni ricorsive. L’operatore di minimalizzazione, generalmente indicato con µ, interviene nella costruzione di funzioni ricorsive generali che non siano funzioni primitive ricorsive a partire dalle funzioni base. La possibilità di utilizzare l’operatore della minimalizzazione, oltre a quelle della composizione e della ricorsione, per costruire una funzione amplia l’insieme delle funzioni ricorsive primitive all’insieme delle funzioni ricorsive generali. Le più comuni funzioni calcolabili sono infatti primitive ricorsive e per costruirle a partire dalle funzioni base (funzione zero, funzione successore e funzioni di proiezione) sono sufficienti i procedimenti di composizione e ricorsione. Tuttavia, come dimostrato da W. Ackermann con la funzione che porta il suo nome (→ Ackermann, funzione di), le funzioni primitive ricorsive non esauriscono l’insieme delle funzioni calcolabili. Per la costruzione di un modello teoricamente esaustivo del concetto di calcolabilità (→ Church, tesi di) occorre introdurre come procedimento costruttivo anche lo schema della minimalizzazione. L’insieme delle funzioni così ottenuto è l’insieme delle funzioni ricorsive: queste sono tutte e sole quelle che si ottengono dalle funzioni base con l’applicazione dei tre schemi costruttivi, di composizione, ricorsione e minimalizzazione. L’operatore µ di minimalizzazione agisce su una funzione di n + 1 variabili e individua il più piccolo valore di una di esse che rende la funzione uguale a 0. Tale valore è funzione delle rimanenti n variabili; precisamente:
• data una funzione g(x1, ..., xn, y) ricorsiva tale che per ogni n-pla (x1, x2, ..., xn) esista un numero y che verifichi l’uguaglianza g(x1, ..., xn, y) = 0;
• si indica con µy(g(x1, ..., xn, y) = 0) il più piccolo numero naturale y tale che g(x1, ..., xn, y) = 0;
• si definisce la funzione ricorsiva di n variabili ƒ(x1, ..., xn) = µy(g(x1, ..., xn, y) = 0).
La funzione ƒ è stata ottenuta da g per mezzo del µ-operatore.