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 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 smn, la notation originale utilisée par Kleene est devenue la terminologie standard pour le concept.
Définition
modifier![T(int f(int n) { return n==1?:n%2==0?f(n/2):f(3*n+1); }, 5, f(5)=f(16)=f(8)=f(4)=f(2)=f(1)=1)](http://upload.wikimedia.org/wikipedia/commons/d/dd/KleeneT_collatz5.gif)
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 est obtenu en formalisant cette simulation.
Le prédicat prend trois nombres naturels comme arguments. est vraie si est le nombre d'étapes nécessaires pour que la machine de Turing qu'encode s'arrête sur l'entrée [1]. La première définition qu'avait donnée Kleene remplaçait par un codage de la trace d'éxecution de la machine lancée sur , et 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 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 transitions successives en utilisant les transitions codées par , en utilisant comme état initial l'entrée .
- Enfin, si au bout de transitions, le calcul de sur vient de se terminer, il renvoie vrai, sinon, on renvoie faux.
Il y a une fonction récursive primitive , telle que renvoie le résultat inscrit sur la bande de calcul par au bout de étapes lorsqu'on lance la machine sur . Ainsi, si est vraie, alors renvoie la sortie de la fonction que représente sur l'entrée .
Pour chaque entier , il est possible de définir le prédicat et la fonction , analogues à et , qui prennent entrées au lieu d'une seule[5].
Comme et , et 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 et , par exemple l'arithmétique de Robinson ou des théories plus fortes comme l'arithmétique de Peano[6]. Le prédicat permet par exemple de représenter que la machine de Turing encodée par termine sur une entrée donnée , par la formule .
Théorème de la forme normale
modifierLes prédicats 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 est récursive générale si et seulement s'il existe un nombre tel que pour tout entiers , on a
où est l' opérateur de minimisation non bornée ( est le plus petit nombre naturel pour lequel est vrai, et n'est pas défini s'il n'y en a pas) et 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 et , qui sont indépendants de la fonction calculable 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
modifierEn 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 , le prédicat sur
où les désignent une alternance de quantificateurs qui terminent par un , est -complet. En particulier, a le même degré de Turing que le problème de l'arrêt, et est donc indécidable.
Bibliographie
modifier- (en) Stephen Cole Kleene, Mathematical logic, Mineola, New York, Dover Publications, (ISBN 978-0486425337, lire en ligne
).
- (en) Stephen Cole Kleene, Introduction To Metamathematics, North Holland, (ISBN 978-0720421033, lire en ligne
).
Références
modifier- (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).
- Kleene 1966, p. 243
- (en) Stephen Cole Kleene, « Recursive predicates and quantifiers », Transactions of the American Mathematical Society, vol. 53, no 1, , p. 41–73 (ISSN 0002-9947 et 1088-6850, DOI 10.1090/S0002-9947-1943-0007371-8
)
- Kleene 1952, p. 281
- Kleene 1966, p. 244
- Kleene 1966, p. 269
- Kleene 1952, p. 296
- Kleene 1952, p. 288
- Kleene 1966, p. 271