On considère une fonction récursive {f}», d’argument {x.} On dit que « {f(x)} termine » quand l’appel {f(x)} conduit à un résultat en un temps fini, et que « {f} termine quand {f(x)} termine pour tous ses arguments {x} possibles.
Théorème (Terminaison) Soit {f} une fonction récursive, définie sur {\mathcal{A}.} Soit {\phi} une application de {\mathcal{A}} dans {(E,\preceq )} bien fondé. Soit {\mathcal{B}} l’ensemble des {x\in \mathcal{A}} tels que {\phi (x)} est minimal dans {\phi (\mathcal{A})(}les éléments de {\mathcal{B}} sont appelés les cas de base). On suppose que {f(b)} termine pour tous les cas de base {b.} Pour tout {x\in \mathcal{A},} on suppose que les appels récursifs dans {f(x)} sont en nombre fini et du type {f(y)} avec {\phi (y)\prec \phi (x).} Alors, sous ces hypothèses, la fonction {f} termine.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres