Une application des entrées encodées de façon finie (classiquement des mots finis ou des entiers naturels) vers des sorties telle qu'il existe une procédure finie exécutable mécaniquement qui, pour chaque entrée valide, s'arrête et fournit la sortie correcte.

Principe

La calculabilité est l'existence d'une procédure effective et finie : une recette unique qui transforme toute entrée autorisée en sa sortie en un nombre fini d'étapes déterministes.

Démonstration

L'addition des entiers naturels réalisée par une machine de Turing : données deux notations, la machine s'arrête avec la notation de leur somme.

Mauvaise application

Prétendre qu'une fonction à valeurs réelles est calculable sans spécifier un codage des réels ou un critère d'arrêt, ou confondre des routines d'approximation numérique avec une calculabilité exacte.

Conséquence

Si une fonction est calculable, on peut mécaniser son évaluation, démontrer des propriétés de décidabilité de son graphe et l'utiliser dans des réductions formelles entre problèmes de décision.

Inversion

Une fonction non calculable : il n'existe aucune algorithmie finie qui s'arrête avec les sorties correctes pour toutes les entrées valides.

Limite

S'applique seulement aux fonctions dont les entrées/sorties ont un encodage fini effectif ; exclut les fonctions réelles non représentées, les modèles à oracle ou hypercalcul et les affirmations selon lesquelles des approximations probabilistes impliquent une calculabilité exacte.

Tension sémantique

Souvent confondue avec la décidabilité d'un ensemble (décision d'appartenance) ou avec l'approximabilité numérique ; la fonction calculable concerne la génération explicite de sorties pour chaque entrée, pas seulement l'appartenance à un ensemble ou la qualité d'approximation.

Synthèse

Une fonction calculable est une application entre objets représentables finiment pour laquelle une procédure mécanique finie fournit des sorties exactes pour chaque entrée permise.