Prédicat T et fonction U de Kleene

En calculabilité, le prédicat T, étudié pour la première fois par le mathématicien Stephen Cole Kleene, est un ensemble particulier de triplets de nombres naturels utilisé pour représenter des fonctions calculables dans les théories formelles de l'arithmétique . De manière informelle, le prédicat $T$ indique si un programme informatique donné, lancé sur une entrée particulière, nécessitera un certain nombre d'étapes de calcul pour terminer, et la fonction U est utilisée pour obtenir les résultats du calcul si le programme s'arrête. Comme pour le théorème s_mn, la notation originale utilisée par Kleene est devenue la terminologie standard pour le concept.

Définition

Illustration du prédicat T. Le premier argument, en bleu, représente le code de la fonction (ici, la fonction de Collatz), donnée dans le langage C plutôt que dans un codage de Gödel. Le deuxième argument, en rouge, est le nombre 5, qui représente l'entrée de la fonction. Le troisième argument, en vert, représente la suite des étapes de calcul pour obtenir le résultat final, 1.

La définition dépend d'un codage de Gödel adéquat qui encode les machines de Turing comme des entiers naturels. Ce codage doit permettre, étant donnés l'index de la fonction, de simuler le calcul de la fonction sur une entrée donnée. Le prédicat $T$ est obtenu en formalisant cette simulation.

Le prédicat $T(e,i,t)$ prend trois nombres naturels comme arguments. $T(e,i,t)$ est vraie si $t$ est le nombre d'étapes nécessaires pour que la machine de Turing qu'encode $e$ s'arrête sur l'entrée $i$. La première définition qu'avait donnée Kleene remplaçait $t$ par un codage de la trace d'éxecution de la machine lancée sur $i$, et $T$ décidait si cette trace était bien une trace valide et qui correspondait à un calcul terminé. Dans tous les cas, ce prédicat est décidable et primitif récursif. Il peut être décidé par l'algorithme suivant :

• Tout d'abord, l'algorithme détermine si $e$ est bien le code d'une machine de Turing. Si ce n'est pas le cas, il renvoie faux, sinon, on passe à l'étape suivante.
• Ensuite, il effectue $t$ transitions successives en utilisant les transitions codées par $e$, en utilisant comme état initial l'entrée $i$.
• Enfin, si au bout de $t$ transitions, le calcul de $e$ sur $i$ vient de se terminer, il renvoie vrai, sinon, on renvoie faux.

Il y a une fonction récursive primitive $U$, telle que $U(e,i,t)$ renvoie le résultat inscrit sur la bande de calcul par $e$ au bout de $t$ étapes lorsqu'on lance la machine sur $i$. Ainsi, si $T(e,i,t)$ est vraie, alors $U(e,i,t)$ renvoie la sortie de la fonction que représente $e$ sur l'entrée $i$.

Pour chaque entier $k\geq 1$, il est possible de définir le prédicat $T_{k}(e,i_{1},\dots ,i_{k},t)$ et la fonction $U_{k}(e,i_{1},\dots ,i_{k},t)$, analogues à $T$ et $U$, qui prennent $k$ entrées au lieu d'une seule.

Comme $T$ et $U$, $T_{k}$ et $U_{k}$ sont aussi primitifs récursifs. De ce fait, toute théorie arithmétique capable de représenter chaque fonction récursive primitive est capable de représenter $T$ et $U$, par exemple l'arithmétique de Robinson ou des théories plus fortes comme l'arithmétique de Peano. Le prédicat $T$ permet par exemple de représenter que la machine de Turing encodée par $e$ termine sur une entrée donnée $i$, par la formule $\exists t,T(e,i)$.

Théorème de la forme normale

Les prédicats $T_{k}$ peuvent être utilisés pour obtenir le théorème de forme normale de Kleene pour les fonctions calculables. Il énonce qu'une fonction $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ est récursive générale si et seulement s'il existe un nombre $e$ tel que pour tout entiers $n_{1},\ldots ,n_{k}$, on a

$f(n_{1},\ldots ,n_{k})\simeq U_{k}(e,n_{1},\ldots ,n_{k},\mu t.T_{k}(e,n_{1},\ldots ,n_{k},t))$

où $\mu$ est l' opérateur de minimisation non bornée ($\mu x.\phi (x)$ est le plus petit nombre naturel $x$ pour lequel $\phi (x)$ est vrai, et n'est pas défini s'il n'y en a pas) et $\simeq$ est vrai si les deux côtés sont indéfinis ou si les deux sont définis et qu'ils sont égaux. Par ce théorème, la définition de chaque fonction récursive générale f peut être réécrite sous une forme normale dans laquelle l'opérateur μ ne soit utilisé qu'une seule fois, le reste des calculs étant contenus dans $U_{k}$ et $T_{k}$, qui sont indépendants de la fonction calculable $f$ et primitifs récursifs. Cela permet de démontrer notamment que les fonctions calculées par les machines de Turing sont toutes des fonctions générales récursives.

Hiérarchie arithmétique

En plus d'encoder la calculabilité, le prédicat T peut être utilisé pour générer des ensembles complets dans la hiérarchie arithmétique, et pour démontrer le théorème de Post. En particulier, pour tout $n$, le prédicat sur $e$

$Q_{1}x_{1}\cdots Q_{n}x_{n}T_{n}(e,e,x_{1},\dots ,x_{n})$

où les $Q_{i}$ désignent une alternance de $n$ quantificateurs qui terminent par un $\exists$, est $\Sigma _{n}^{0}$-complet. En particulier, $\exists t,T_{1}(e,e,t)$ a le même degré de Turing que le problème de l'arrêt, et est donc indécidable.

Bibliographie

• (en) Stephen Cole Kleene, Mathematical logic, Mineola, New York, Dover Publications, 1966 (ISBN 978-0486425337, lire en ligne ).
• (en) Stephen Cole Kleene, Introduction To Metamathematics, North Holland, 1952 (ISBN 978-0720421033, lire en ligne ).

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kleene's T predicate » (voir la liste des auteurs).