title: Théorème d'itération
text: # Théorème d'itération
  
  Le théorème d'itération est dû à Stephen Kleene, il est aussi connu sous le nom de théorème $s_{mn}$ dans sa forme paramétrisée.
  
  ## Énoncé
  
  ### Pour une énumération de fonction récursive
  
  Si $\varphi ~$ est une énumération acceptable, alors il existe une fonction partielle récursive $s~$ telle que pour tout indice $\mathbf {e} ~$ et tous nombres $x~$ et $y~$
  
  $\varphi _{s(\mathbf {e} ,x)}(y)=\varphi _{\mathbf {e} }(x,y)$.
  
  ### Pour un langage de programmation
  
  Si $\varphi$ est un langage de programmation acceptable alors il existe une fonction calculable $s~$ telle que pour tout programme $\mathbf {e}$ et tous $x~$ et $y~$
  
  $\varphi _{s(\mathbf {e} ,x)}(y)=\varphi _{\mathbf {e} }(x,y)$.
  
  $s$ est appelée fonction d'itération ou fonction s-m-n dans sa forme paramétrisée.
  
  ## Évaluation partielle
  
  La fonction d'itération est un des points fondamentaux de l'évaluation partielle. En effet, dans $\varphi _{s(\mathbf {e} ,x)}(y)=\varphi _{\mathbf {e} }(x,y)$, le programme $s(\mathbf {e} ,x)$ peut être vu comme la spécialisation du programme $\mathbf {e}$ pour l'entrée $x~$, en d'autres termes, le programme $\mathbf {e}$ dont la première entrée a été fixée pour la valeur $x~$. Pour cette notion, on pourra se référer aux travaux de N. Jones.
  
  ## Auto-référence
  
  Par $s(x,x)~$, ce théorème permet de construire des programmes faisant référence à leurs propres codes puisque $\varphi _{s(x,x)}(y)=\varphi _{x}(x,y)$. En particulier, $s(x,x)~$ est fondamental dans la construction d'une machine de Turing dont l'arrêt est indécidable ou dans la preuve du théorème de récursion de Kleene.
  
  ## Exemple
  
  Le programme Python suivant implémente la fonction $s_{11}$ pour une fonction quelconque f et une variable x :
  
  Appliqué à la fonction d'addition entre deux nombres :
  
  Dans l'exemple précédent, g s'écrit autrement $g:x\mapsto (y\mapsto x+y)$.
  
  