Pour toute machine de Turing M,

• on note \displaystyle \vdash_{M}^{*} la fermeture réflexive transitive de \vdash_M .
• On dit que la configuration C_1 produit la configuration C_2 si et seulement si \displaystyle C_1 \vdash_{M}^{*} C_2
• Un calcul de C_2 à partir de C_1 est une suite de configurations

  C_1 = C^{\left(0\right)} \vdash_M C^{\left(1\right)} \vdash_M C^{\left(2\right)} \vdash_M \cdots \vdash_M C^{\left(n\right)}= C_2

On dit alors qu'on a un calcul de longueur n, et on note

Y a-t-il moyen de mieux poser les super et sub params sur les dérives? En notons au passage que \vdash est \vdash.