Fonction Calculable


Fonction Calculable

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 Turing «qui termine».

Exemples

  • Les programmes informatiques qui s'arrêtent (lors de leur exécution sur n'importe quelle entrée) sont des fonctions calculables.
  • La fonction qui prend en entrée une machine de Turing (représenté par un entier) et une entrée pour cette machine et leur associe 1 si la machine s'arrête sur cette entrée, 0 sinon, n'est pas calculable (pour plus d'information voir l'article Problème de l'arrêt).

Voir aussi


  • Portail de l’informatique Portail de l’informatique
  • Portail de la logique Portail de la logique
Ce document provient de « Fonction calculable ».

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • 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 — 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

  • Calculable — Calculabilité La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les …   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

  • calculable — [ kalkylabl ] adj. • 1732; de calculer ♦ Qui peut se calculer. N. f. CALCULABILITÉ . ⊗ CONTR. Incalculable. ● calculable adjectif Qui peut se calculer : Un risque calculable. ● calculable (synonymes) adjectif Qui peut se calcule …   Encyclopédie Universelle

  • Fonction Semi-Calculable — En informatique théorique, les fonctions semi calculables ou fonctions partielles récursives sont les fonctions calculables par les machines de Turing ou tout autre système de programmation Turing complet. En logique mathématique les fonctions… …   Wikipédia en Français

  • Fonction D'état — Une fonction d état est, dans l étude d un système thermodynamique, une fonction des variables d état qui décrivent ses états d équilibre. Physiquement, une telle fonction représente une propriété du système qui ne dépend que de l état dans… …   Wikipédia en Français

  • Fonction d'etat — Fonction d état Une fonction d état est, dans l étude d un système thermodynamique, une fonction des variables d état qui décrivent ses états d équilibre. Physiquement, une telle fonction représente une propriété du système qui ne dépend que de l …   Wikipédia en Français

  • Fonction d'état, variable d'état, équation d'état — Fonction d état Une fonction d état est, dans l étude d un système thermodynamique, une fonction des variables d état qui décrivent ses états d équilibre. Physiquement, une telle fonction représente une propriété du système qui ne dépend que de l …   Wikipédia en Français