Système T

système formel de la logique mathématique

À l'instar de la récursion primitive ou le lambda-calcul, le Système T est un langage de programmation théorique. Il a été inventé par le logicien Kurt Gödel.

Ce système consiste en une fusion de la récursion primitive et du lambda-calcul simplement typé. Le système T est plus expressif que les deux précédemment cités étant donné qu'il permet par exemple de définir la fonction d'Ackermann.

Le principe est simple : on garde les schémas récursifs primitifs :

La différence majeure c'est que l'on autorise les paramètres à être des fonctions. Par rapport à la récursion primitive, il est alors possible, par exemple, de faire une récurrence sur plusieurs paramètres.

Formalisme modifier

Le formalisme de Martin-Löf utilise (entre autres) les notations suivantes :

  • Une expression peut être simple (en : single) ou combinée (en : combined). Une expression simple correspond à un 1-uplet, une expression multiple à un n-uplet.
  • Une expression peut être saturée (en : satured) ou non-saturée (en : unsatured). Une expression saturée est une variable ou une constante. Inversement, une expression non-saturée est un opérateur qui attend qu'on lui fournisse des paramètres de manière à pouvoir être  -réduit en une variable ou une constante.
  • Une notion d'arité, dont il est dit : "D'un certain point de vue ça ressemble au lambda calcul simplement typé" [Programming in Martin-Löf type theory, page 21].

Définition :

  • 0 est une arité ; l'arité d'une expression simple et saturée.
  • si     sont des arités, alors   est une arité ; l'arité des expressions combinées.
  • si   et   sont des arités, alors   est une arité ; l'arité des expressions non saturées.
  • Le type d'un élément est noté en exposant. Ex :  
  • Les arguments attendus par un opérateur (une expression non-saturée) sont notés entre deux parenthèses précédant l'opérateur. Ex :  

Selon le formalisme de Martin-Löf on peut écrire les termes du système T par récurrence

  •   : de type  
  • si   est un terme de type   alors   est un terme de type  
  • les variables     de type   sont des termes de type  
  • si   est une variable de type   et   un terme de type   alors   est un terme de type   (abstraction)
  • si   est un terme de type   et   un terme de type   alors   est un terme de type   (application)
  • si   un terme de type   et que   et   sont des termes de type   alors   est un terme de type  

Pour comprendre comment fonctionne ce système il faut naturellement des règles de réduction.

  •  
  •  
  •  

On garde les notions de substitution du lambda-calcul et de la récursion primitive, ainsi que les « règles additionnelles » qui permettent de réduire « à l'intérieur » d'un terme.

Quelques théorèmes importants modifier

  • tous les termes clos (sans variables libres) de type N sont des numéraux (un Sn(0))
  • tous les termes clos de type N sont normalisables

Exemples modifier

La fonction d'Ackermann modifier

La fonction d'Ackermann que l'on ne peut pas programmer en récursion primitive est définie par les équations suivantes :

  • Ack 0 p = S(p)
  • Ack S(n) 0 = Ack n S(0)
  • Ack S(n) S(p) = Ack n (Ack S(n) p)

Ces équations n'ont pas la forme voulue mais en modifiant un peu on obtient la forme désirée :

  • Ack 0 = λp.S(p)
  • Ack S(n) = λp.Ack' p (Ack n)
  • Ack' 0 f = f S(0)
  • Ack' S(p) f = f (Ack' p f)

Il n'y a plus qu'à écrire cela sous forme de terme :

 

Un minimum efficace modifier

En récursion primitive, on ne peut pas faire une fonction qui retourne le minimum de deux entiers en temps de calcul minimum de ces deux entiers. C'est très contraignant par exemple si on calcule le minimum de 2 et 1 000 000. Comme avec le système T on peut s'arranger pour faire des récursions sur plusieurs paramètres, ne nous gênons pas.

Équations intuitives :

  • Min 0 p = 0
  • Min S(n) 0 = 0
  • Min S(n) S(p) = S(Min n p)

En transformant un peu on obtient des équations utilisant le schéma souhaité :

  • Min 0 = λp.0
  • Min S(n) = λp.Min' p (Min n)
  • Min' 0 f = 0
  • Min' S(p) f = S(f p)

Le terme voulu est :

 

De la même manière, on peut obtenir facilement un programme optimisé pour l'addition et la soustraction.

Le prédécesseur modifier

pred 0=0

pred s(n)=n

ecriture avec le rec

pred=λx(rec x 0 λxλh x)

Articles connexes modifier