Funzione ricorsiva

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Funzioni ricorsive)
Vai alla navigazione Vai alla ricerca

Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo. Infatti nella teoria della calcolabilità si mostra che le funzioni ricorsive corrispondono precisamente a quelle funzioni che possono essere calcolate tramite una macchina di Turing.

Le funzioni ricorsive sono un sovrainsieme delle funzioni ricorsive primitive, ed infatti la loro definizione induttiva (come vedremo nel seguito) è costruita a partire da quella di queste ultime. Esistono quindi funzioni ricorsive che non sono anche ricorsive primitive, e l'esempio più noto è quello della funzione di Ackermann. Altre classi di funzioni equivalenti a quella delle funzioni ricorsive sono le funzioni λ-ricorsive e le funzioni che possono essere calcolate da un algoritmo di Markov.

Le funzioni ricorsive sono definite sulla base delle funzioni ricorsive primitive.

Le funzioni ricorsive sono la più piccola classe di funzioni contenente le funzioni ricorsive primitive chiusa rispetto agli operatori di composizione, di ricorsione primitiva e all'operatore μ, detto anche operatore di minimizzazione.

L'operatore μ è così definito:

Minimizzazione : data una funzione totale :

Le funzioni ricorsive primitive sono quindi un sottoinsieme delle funzioni ricorsive. Si noti che mentre le funzioni ricorsive primitive sono sempre totali (il viceversa non è vero), le funzioni ricorsive possono essere parziali, ovvero possono non essere definite per alcuni valori di input: infatti, l'operatore minimizzazione non restituisce alcun valore nel caso in cui la funzione a cui è applicato non si annulla per nessun valore dell'argomento.

Si ricorda comunque che l'operatore di minimizzazione opera su funzioni totali. Si può dimostrare che se si ammette l'applicazione dell'operatore di minimizzazione su funzioni parziali, allora le funzioni ricorsive non sarebbero chiuse rispetto alla minimizzazione.

Esempi di funzioni ricorsive

[modifica | modifica wikitesto]

Esempio di programma

[modifica | modifica wikitesto]

In informatica, ecco un esempio di funzione ricorsiva: function factorial(n)

  if n == 0 then
return 1
end
return n * factorial(n - 1)
end

Limitazioni: funzioni non ricorsive

[modifica | modifica wikitesto]

Non tutte le funzioni sono calcolabili, cioè ricorsive. Ecco alcuni esempi.

Il problema della fermata

[modifica | modifica wikitesto]

Consideriamo una qualunque enumerazione delle funzioni ricorsive, in cui la funzione corrisponde alla -esima funzione ricorsiva. Cioè detta la -esima funzione ricorsiva, abbiamo:

Allora, non esiste nessuna funzione ricorsiva tale che per ogni e

Questo problema è una formulazione del problema della fermata. Si veda l'apposita sezione nell'articolo sugli insiemi ricorsivi per una formulazione alternativa.

Dimostrazione

[modifica | modifica wikitesto]

Supponiamo per ipotesi che sia ricorsiva. Allora lo sarebbe anche una funzione così definita:

Diciamo che nell'enumerazione delle funzioni ricorsive che abbiamo dato, sia l'indice della funzione , e che quindi .
Se passiamo l'indice (che è un numero naturale) come parametro alla funzione , abbiamo .
Per la definizione di abbiamo che se e solo se .
Ma per la definizione di abbiamo che se e solo se non è definita.
Ricapitolando se e solo se , che è come dire che se e solo se non è definita, che è assurdo.
Quindi questa dimostrazione per assurdo mostra che l'ipotesi iniziale " è ricorsiva" è falsa.

  • Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; Franco Angeli Editore: Linguaggi, Modelli, Complessità, 2003. ISBN 88-464-4470-1
  • Brainerd, W. S., Landweber, L. H., Theory of Computation, Wiley, 1974. ISBN 0471095850

Voci correlate

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
Controllo di autoritàThesaurus BNCF 45388 · LCCN (ENsh85112014 · BNF (FRcb11977577z (data) · J9U (ENHE987007565763305171