Fonction partielle récursive

Fonction partielle récursive

Les fonctions partielles récursives correspondent aux fonctions calculées par une machine de Turing. Selon la thèse de Church la classe des fonctions partielles récursives est exactement l'ensemble des fonctions pouvant être décrites par un algorithme (ou tout mécanisme de calcul).

D'un point de vue plus formel, elles correspondent aux relations fonctionnelles \Sigma_1~ (Hiérarchie arithmétique).


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction partielle récursive de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Fonction Partielle Récursive — Les fonctions partielles récursives correspondent aux fonctions calculées par une machine de Turing. Selon la thèse de Church la classe des fonctions partielles récursives est exactement l ensemble des fonctions pouvant être décrites par un… …   Wikipédia en Français

  • Fonction partielle recursive — Fonction partielle récursive Les fonctions partielles récursives correspondent aux fonctions calculées par une machine de Turing. Selon la thèse de Church la classe des fonctions partielles récursives est exactement l ensemble des fonctions… …   Wikipédia en Français

  • Fonction partielle — En mathématiques une fonction partielle sur un ensemble donné E est une fonction définie sur une partie de celui ci, qui est alors appelé domaine de définition de la fonction partielle. Cette notion apparait en particulier en théorie de la… …   Wikipédia en Français

  • Fonction Récursive — Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

  • Fonction recursive — Fonction récursive Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

  • Fonction Calculable — Une fonction calculable (ou fonction récursive) est une fonction semi calculable (ou fonction partielle récursive) qui est aussi totale, c est à dire définie pour toute entrée (en tout point). Ce sont les fonctions calculées par une machine de… …   Wikipédia en Français

  • Fonction récursive — Sur les autres projets Wikimedia : « Fonction récursive », sur le Wiktionnaire (dictionnaire universel) En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de… …   Wikipédia en Français

  • Fonction calculable — Une fonction calculable (ou fonction récursive) est une fonction semi calculable (ou fonction partielle récursive) qui est aussi totale, c est à dire définie pour toute entrée (en tout point). Ce sont les fonctions calculées par une machine de… …   Wikipédia en Français

  • Fonction d'Ackermann — Dans la théorie de la récursivité, la fonction d Ackermann (aussi appelée fonction d Ackermann Péter), est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la… …   Wikipédia en Français

  • Fonctions récursives — Fonction récursive Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”