funzioni ricorsive

funzioni ricorsive

Classe delle funzioni computabili o algoritmiche, ossia delle funzioni n-arie f tali che esiste un algoritmo per computare il valore f(x₁,...,x_{[) per ogni n-pla di numeri naturali (x₁,...,x_{[). Esse si def iniscono a partire da tre funzioni iniziali mediante tre regole. Le funzioni iniziali sono la funzione zero z(x)=0, la funzione successore s(x)=x+1 (si scrive anche s(x)=x′), la funzione selezione i(x₁,...,x_{[)=x_〈 con 1≤k≤n. Vi sono varie regole per ottenere nuove funzioni da quelle date: regola di sostituzione, regola di induzione, regola di minimalizzazione normale o regola di minimalizzazione limitata. Si dicono funzioni ricorsive primitive le funzioni che si possono ottenere dalle funzioni iniziali mediante un numero finito di applicazioni delle regole di sostituzione e di induzione. Esempi di funzioni ricorsive primitive sono le comuni funzioni aritmetiche elementari (predecessore di x, controsegno di x, fattoriale di x, somma di x e y, prodotto di x e y, esponenziale di x e y, differenza aritmetica di x e y, differenza assoluta di x e y, kroneckeriano di x e y, eguaglianza di x e y, minimo di x e y, massimo di x e y, resto della divisione di y per x, quoziente della divisione di y per x). Si dicono ricorsive generali le funzioni che si possono ottenere dalle funzioni iniziali mediante un numero finito di applicazioni delle regole di sostituzione, induzione e minimalizzazione illimitata normale. La classe delle funzioni ricorsive generali contiene pertanto quella delle funzioni ricorsive primitive. È anche facile persuadersi che le funzioni ricorsive generali sono intuitivamente computabili. La tesi di Alonzo Church (1936) afferma che tutte le funzioni intuitivamente computabili sono ricorsive generali. Accolta questa tesi, risulta precisato il concetto intuitivo di computabilità e, conseguentemente, quello di decidibilità e di costruibilità.

→ Programmazione, algoritmi di