Prédicat T et fonction U de Kleene

Cet article est orphelin. Moins de trois articles lui sont liés (août 2024).

Vous pouvez aider en ajoutant des liens vers [[Prédicat T et fonction U de Kleene]] dans les articles relatifs au sujet.

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 ${\displaystyle 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.

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 ${\displaystyle T}$ est obtenu en formalisant cette simulation.

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

• Tout d'abord, l'algorithme détermine si ${\displaystyle 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 ${\displaystyle t}$ transitions successives en utilisant les transitions codées par ${\displaystyle e}$, en utilisant comme état initial l'entrée ${\displaystyle i}$.
• Enfin, si au bout de ${\displaystyle t}$ transitions, le calcul de ${\displaystyle e}$ sur ${\displaystyle i}$ vient de se terminer, il renvoie vrai, sinon, on renvoie faux.

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

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

Comme ${\displaystyle T}$ et ${\displaystyle U}$, ${\displaystyle T_{k}}$ et ${\displaystyle 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 ${\displaystyle T}$ et ${\displaystyle U}$, par exemple l'arithmétique de Robinson ou des théories plus fortes comme l'arithmétique de Peano^[6]. Le prédicat ${\displaystyle T}$ permet par exemple de représenter que la machine de Turing encodée par ${\displaystyle e}$ termine sur une entrée donnée ${\displaystyle i}$, par la formule ${\displaystyle \exists t,T(e,i)}$.

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

${\displaystyle 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ù ${\displaystyle \mu }$ est l' opérateur de minimisation non bornée (${\displaystyle \mu x.\phi (x)}$ est le plus petit nombre naturel ${\displaystyle x}$ pour lequel ${\displaystyle \phi (x)}$ est vrai, et n'est pas défini s'il n'y en a pas) et ${\displaystyle \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 ${\displaystyle U_{k}}$ et ${\displaystyle T_{k}}$, qui sont indépendants de la fonction calculable ${\displaystyle 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.

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^[8]. En particulier, pour tout ${\displaystyle n}$, le prédicat sur ${\displaystyle e}$

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

où les ${\displaystyle Q_{i}}$ désignent une alternance de ${\displaystyle n}$ quantificateurs qui terminent par un ${\displaystyle \exists }$, est ${\displaystyle \Sigma _{n}^{0}}$-complet. En particulier, ${\displaystyle \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.

• (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 ).

• (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).

• Portail de la logique
• Portail de l'informatique théorique