fonction calculable

Imaginez une machine qui reçoit un nombre, effectue une suite d'étapes précises et doit toujours rendre un résultat. Une fonction calculable est une règle de ce type : pour chaque entrée autorisée, son calcul finit par s'arrêter. On peut donc attendre une sortie, même si le nombre d'étapes n'est pas le même selon l'entrée. Cette idée concerne les fonctions que les modèles théoriques de l'informatique peuvent effectivement exécuter jusqu'au bout.

Une fonction calculable est une fonction partielle récursive calculée par une procédure qui termine pour toute entrée autorisée. Autrement dit, elle est totale sur le domaine d'entrée fixé : la machine fournit une valeur pour chacune de ces entrées. « Partielle » signifie qu'une règle peut, en général, ne pas fournir de valeur pour certaines entrées ; ici, la condition de totalité écarte cette possibilité sur le domaine considéré. Le synonyme « fonction récursive totale » insiste précisément sur cette couverture complète des entrées.

La définition est opérationnelle : il doit exister une machine de Turing qui reçoit l'argument, termine son calcul et produit la valeur de la fonction. La machine peut prendre un nombre variable d'étapes, mais elle ne peut pas rester indéfiniment en cours d'exécution pour une entrée du domaine. Cette classe de fonctions forme l'objet central de la théorie de la calculabilité.

Une fonction semi-calculable satisfait une exigence plus faible : une machine peut produire la valeur lorsqu'elle existe, sans être tenue de s'arrêter sur toutes les entrées. La fonction calculable se reconnaît donc à la terminaison garantie, et non à une durée d'exécution identique pour toutes les entrées.

Pour décrire une fonction calculable, quatre éléments se répondent. L'entrée est l'argument fourni à la machine. La règle de calcul est la suite finie d'instructions qui transforme cette entrée. La machine de Turing est le modèle abstrait qui exécute ces instructions. Enfin, la sortie est la valeur produite lorsque l'exécution s'arrête.

La sortie dépend de l'entrée et de la règle ; elle n'est donc pas une donnée indépendante. La terminaison relie la machine à la définition de la fonction : sans arrêt, aucune valeur de sortie n'est obtenue pour cette entrée. Le domaine précise les arguments auxquels la garantie s'applique. Ces éléments suffisent à vérifier, pour une entrée donnée, qu'un calcul produit bien une valeur, mais une seule exécution finie ne suffit pas à prouver la terminaison pour toutes les entrées.

Considérons la fonction qui ajoute 1 à un entier naturel. L'entrée est un entier naturel n ; la règle demande de lui ajouter 1 ; la sortie attendue est la valeur f(n).

La règle s'écrit, avec f pour la fonction et n pour l'entrée : $f(n)=n+1f(n)=n+1$.

Pour l'entrée 4, la machine lit 4.
Elle ajoute 1.
Elle obtient 5.
Elle s'arrête et rend 5.

Le même enchaînement s'applique à chaque entier naturel fourni en entrée : la machine effectue l'ajout puis s'arrête. Dans ce cas, la règle illustre une fonction calculable. Le contrôle consiste à vérifier séparément la valeur obtenue et l'arrêt de la procédure.

En informatique théorique, on utilise cette notion pour demander si une tâche possède une procédure effective qui rend une réponse pour toute entrée autorisée. Le geste consiste à préciser le domaine, puis à examiner la terminaison garantie du modèle de calcul.

Pour analyser une règle concrète, on suit une procédure donnée étape par étape et l'on cherche ce qui force l'arrêt. Si l'on ne dispose que d'une procédure qui peut produire une réponse sans garantir son arrêt, la notion de fonction semi-calculable est plus adaptée.

Dans une preuve, une valeur correcte sur quelques entrées ne remplace pas la garantie générale. Il faut relier la règle à une machine de Turing qui termine pour chaque argument du domaine.

Une fonction calculable ne doit pas être confondue avec une fonction semi-calculable. Le critère de définition, ou l'objet d'une preuve de terminaison, est l'arrêt garanti sur toute entrée du domaine : une machine qui peut ne pas s'arrêter sur certaines entrées décrit la seconde situation, pas la première.

Le problème de l'arrêt désigne précisément la difficulté de décider, pour une machine et une entrée quelconques, si le calcul finira. Il ne constitue pas une autre définition de la fonction calculable : il explique pourquoi la garantie de terminaison est une propriété centrale à vérifier.

Le piège principal consiste à observer que la machine s'arrête sur plusieurs entrées, puis à conclure qu'elle s'arrêtera toujours. Le symptôme est une preuve fondée sur des essais finis. Il faut à la place établir une garantie pour chaque entrée du domaine, ou ne pas qualifier la fonction de calculable.

Une entrée sur laquelle la machine ne termine pas suffit à faire perdre la totalité exigée par la définition, si cette entrée appartient au domaine annoncé. La sortie n'est alors pas produite pour ce cas. Il faut préciser le domaine ou employer la description de fonction semi-calculable lorsque seule la production éventuelle d'une valeur est garantie.

La durée du calcul ne fournit pas le critère : elle peut varier d'une entrée à l'autre. Le seuil décisif n'est pas un nombre fixe d'étapes, mais l'arrêt en un nombre fini d'étapes pour chaque entrée du domaine.

L'article « Une fonction qui dépasse les bornes » élargit la réflexion autour de la calculabilité et montre comment une fonction peut dépasser les attentes ordinaires liées au calcul. Cette lecture permet de relier la définition abstraite à une question mathématique plus vaste. Lire l'article.