Fonction calculable

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

  • 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ée 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[modifier | modifier le code]