Julien Marcil - julien.marcil@ift.ulaval.ca
Définition: Une machine de Turing consiste en un 7-tuple de la forme $(S, \Sigma, \Gamma, \delta, \iota, s_{\text{accepte}}, s_{\text{rejete}})$ où
Les machines de Turing formalisent correctement la notion d'algorithme.
Un programme RÉPÉTER implante une fonction
$$ \begin{eqnarray} f : & \mathbb N \times \mathbb N \times \cdots \times \mathbb N & \to & \mathbb N \\ & (r_1, \ r_2, \ \dots, \ r_k) & \mapsto & r_0 \end{eqnarray} $$
Au debut de l’exécution, les registres $r_1$ à $r_k$ contiennent les arguments de $f$, et à la fin, $r_0$ contient $f(r_1, \dots, r_k)$.
$$ \begin{aligned} S \to & \langle\mathtt{INCRÉMENTATION}\rangle S \mid \lambda \mid \\ & \langle\mathtt{AFFECTATION}\rangle S \mid \langle\mathtt{RÉPÉTER}\rangle S \\ \langle\mathtt{INCRÉMENTATION}\rangle \to & \rrinc{V} \\ \langle\mathtt{AFFECTATION}\rangle \to & \rrset{V}{V} \\ \langle\mathtt{RÉPÉTER}\rangle \to & \rrrep{V}[S] \\ V \to & r_N \\ N \to & C \mid CN \\ C \to & 0 \mid 1 \mid 2 \mid 3 \mid 4 \mid 5 \mid 6 \mid 7 \mid 8 \mid 9 \end{aligned} $$
Il est assez facile de faire des programmes RÉPÉTER pour des opérations arithmétiques simples.
$\rrmacro{PLUS}{r_1, r_2} = r_1 + r_2$
$ \rrset{r_0}{r_1} \\ \rrrep{r_2}[ \\ \quad \rrinc{r_0} \\ ] $
$\rrmacro{MULT}{r_1, r_2} = r_1 \times r_2$
$ \rrrep{r_1}[ \\ \quad \rrrep{r_2}[ \\ \quad\quad \rrinc{r_0} \\ \quad ] \\ ] $
$\rrmacro{EXP}{r_1, r_2} = r_1^{r_2}$
$ \rrinc{r_0} \\ \rrrep{r_2}[ \\ \quad \rrset{r_3}{r_4} \\ \quad \rrrep{r_0}[ \\ \quad\quad \rrrep{r_1}[ \\ \quad\quad\quad \rrinc{r_3} \\ \quad\quad ] \\ \quad ] \\ \quad \rrset{r_0}{r_3} \\ ] $
L'instruction $\rrinvoke{r_i}{PROC}{r_{j_1}, \dots, r_{j_k}}$ signifie que l’on doit substituer à cette ligne un bloc d’instructions qui a pour effet de remplacer le contenu du registre $r_i$ par la valeur calculee par $\rrmacro{PROC}{r_{j_1}, \dots, r_{j_k}}$, en renommant au besoin les variables qui apparaissent dans le code de la procédure $\mathtt{PROC}$.
Les appels recursifs ne sont pas permis.
L’instruction $\rrset{r_i}{k}$ signifie que l’on doit substituer à cette ligne $k$ incrémentations, ce qui aura pour effet d’affecter la constante $k$ au registre $r_i$
Partout, on peut mettre une constante $k$ au lieu d’utiliser une variable auxiliaire qu’on aurait incrémentée $k$ fois.
$\rrmacro{EXP}{r_1, r_2} = r_1^{r_2}$
$ \rrset{r_0}{1} \\ \rrrep{r_2}[ \\ \quad \rrinvoke{r_0}{MULT}{r_0,r_1} \\ ] $
Est-il possible de faire n'importequel opérations arithmétiques avec des programmes RÉPÉTER?
$\rrmacro{DEC}{r_1} = \max(0, r_1-1)$
$ \rrrep{r_1}[ \\ \quad \rrset{r_0}{r_2} \\ \quad \rrinc{r_2} \\ ] $
$\rrmacro{MOINS}{r_1, r_2} = \max(0, r_1-r_2)$
$ \rrset{r_0}{r_1} \\ \rrrep{r_2}[ \\ \quad \rrinvoke{r_0}{DEC}{r_0} \\ ] $
$\rrmacro{FACT}{r_1} = r_1 !$
$ \rrset{r_0}{1} \\ \rrrep{r_1}[ \\ \quad \rrinc{r_2} \\ \quad \rrinvoke{r_0}{MULT}{r_0, r_2} \\ ] $
Nous adoptons les conventions syntaxiques suivantes :
Pour évaluer $\langle\mathtt{BLOC}\rangle$ conditionnellement à la valeur booléennes $r_i$ on répète $\langle\mathtt{BLOC}\rangle$ $r_i$ fois.
L’instruction $\rrif{r_i}[\langle\mathtt{BLOC}\rangle]$ sera mise pour $\rrrep{r_i}[\langle\mathtt{BLOC}\rangle]$.
$\rrmacro{ET}{r_1, r_2} = r_1 \land r_2$
$ \rrinvoke{r_0}{MULT}{r_1, r_2} $
$\rrmacro{NEG}{r_1} = \neg r_1$
$ \rrinvoke{r_0}{MOINS}{1, r_1} $
$\rrmacro{OU}{r_1, r_2} = r_1 \lor r_2$ $= \neg(\neg r_1 \land \neg r_2)$
$ \rrinvoke{r_1}{NEG}{r_1} \\ \rrinvoke{r_2}{NEG}{r_2} \\ \rrinvoke{r_0}{ET}{r_1, r_2} \\ \rrinvoke{r_0}{NEG}{r_0} \\ $
$\rrmacro{PG?}{r_1, r_2} = (r_1 \gt r_2)$
$ \rrinvoke{r_3}{MOINS}{r_1, r_2} \\ \rrrep{r_3}[ \\ \quad \rrset{r_0}{\rrtrue} \\ ] $
Regardons d'autres opérations arithmétiques plus complèxes.
$\rrmacro{DIV}{r_1, r_2} = \big\lfloor \frac{r_1}{r_2} \big\rfloor$
$ \rrrep{r_1}[ \\ \quad \rrinvoke{r_3}{PLUS}{r_3, r_2} \\ \quad \rrinvoke{r_4}{PG?}{r_3, r_1} \\ \quad \rrinvoke{r_4}{NEG}{r_4} \\ \quad \rrif{r_4} [ \\ \quad\quad \rrinc{r_0} \\ \quad ] \\ ] $
$\rrmacro{MOD}{r_1, r_2} = r_1~\text{mod}~r_2$
$ \rrinvoke{r_0}{DIV}{r_1, r_2} \\ \rrinvoke{r_0}{MULT}{r_0, r_2} \\ \rrinvoke{r_0}{MOINS}{r_1, r_0} $
$\rrmacro{PREMIER?}{r_1} = (r_1 \in \mathbb P$)
$ \rrset{r_0}{\rrfalse} \\ \rrinvoke{r_5}{PG?}{r_1, 1} \\ \rrif{r_5} [\\ \quad \rrset{r_0}{\rrtrue} \\ \quad \rrset{r_3}{1} \\ \quad \rrinvoke{r_2}{MOINS}{r_1, 2} \\ \quad \rrrep{r_2} [\\ \quad\quad \rrinc{r_3} \\ \quad\quad \rrinvoke{r_4}{MOD}{r_1, r_3} \\ \quad\quad \rrinvoke{r_5}{PG?}{1, r_4} \\ \quad\quad \rrif{r_5} [ \rrset{r_0}{\rrfalse} ] \\ \quad ] \\ ] $
$\rrmacro{PREMIERSUIV}{r_1} =$ le plus petit nombre premier plus grand que $r_1$
$ \rrinvoke{r_2}{PLUS}{r_1, 1} \\ \rrinvoke{r_2}{MULT}{r_2, 2} \\ \rrset{r_3}{\rrtrue} \\ \rrrep{r_2} [\\ \quad \rrinc{r_1} \\ \quad \rrinvoke{r_4}{PREMIER?}{r_1} \\ \quad \rrinvoke{r_4}{ET}{r_3, r_4} \\ \quad \rrif{r_4} [\\ \quad\quad \rrset{r_0}{r_1} \\ \quad\quad \rrset{r_3}{\rrfalse} \\ \quad ] \\ ] $
$\rrmacro{PREMIERK}{r_1} =$ le $r_1$-ème nombre premier
$ \rrrep{r_1} [\\ \quad \rrinvoke{r_0}{PREMIERSUIV}{r_0} \\ ] $
Un tableau d’entiers est un $k$-tuple $(a_1, a_2, \dots, a_k)$ que nous stockons dans un registre $r_j$.
Il est possible d'encoder le $k$-tuple $(a_1, a_2, \dots, a_k)$ où $a_i \in \mathbb N$ dans un entier.
Soit $p_n$ le $n$-ième nombre premier. Le $k$-tuple $(a_1, a_2, \dots, a_k)$ est représenté sant ambiguïté par l'entier
$$p_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}$$
$ \begin{eqnarray} (1, 1, 1) & = & 2^1 3^1 5^1 & = & 30 \\ (2, 1, 1, 1) & = & 2^2 3^1 5^1 7^1 & = & 420 \\ (2, 0, 4, 3, 0, 3) & = & 2^2 3^0 5^4 7^3 11^0 13^3 & = & 1883927500 \end{eqnarray} $
$\rrmacro{TABLVAL}{r_1,r_2} =$ le $r_2$-ème élément du tableau $r_1$
$ \rrinvoke{r_3}{PREMIERK}{r_2} \\ \rrset{r_4}{r_3} \\ \rrrep{r_1} [\\ \quad \rrinvoke{r_5}{MOD}{r_1, r_4} \\ \quad \rrinvoke{r_5}{PG?}{1, r_5} \\ \quad \rrif{r_5} [\\ \quad\quad \rrinc{r_0} \\ \quad\quad \rrinvoke{r_4}{MULT}{r_3, r_4} \\ \quad ] \\ ] $
$\rrmacro{TABLASS}{r_1,r_2,r_3} =$ le tableau $r_1$ où $r_2$-ème élément est remplacé par $r_3$
$ \rrinvoke{r_4}{TABLVAL}{r_1,r_2} \\ \rrinvoke{r_5}{PREMIERK}{r_2} \\ \rrinvoke{r_6}{EXP}{r_5,r_4} \\ \rrinvoke{r_0}{DIV}{r_1,r_6} \\ \rrinvoke{r_7}{EXP}{r_5,r_3} \\ \rrinvoke{r_0}{MULT}{r_0,r_7} $
Il semble que les programmes RÉPÉTER peuvent calculer des fonctions complexes.
Peut-on calculer toutes les fonctions à valeurs entières avec un programme RÉPÉTER?
Définition: Les fonctions calculables par un programme RÉPÉTER sont appelées primitives récursives.
Pour une fonction $f : \mathbb N \to \mathbb N$, et un entier $n$, on note :
$$ \begin{align} f^{\langle 0 \rangle}(x) & = x \\ f^{\langle 1 \rangle}(x) & = f(x) \\ f^{\langle 2 \rangle}(x) & = f(f(x)) \\ & \vdots \\ f^{\langle n \rangle}(x) & = \underbrace{f(f(\cdots f(x) \cdots))}_{n~\text{fois}} \\ \end{align} $$
Soit $k, n \in \mathbb N$ et $k \le n$
$$f^{\langle n \rangle}(x) = f^{\langle n-k \rangle}\big(f^{\langle k \rangle}(x)\big)$$
Soit $n, u \in \mathbb N$.
$$\big(f^{\langle n \rangle}\big)^{\langle u \rangle}(x) = f^{\langle nu \rangle}(x)$$
Définition: Soit la fonction $B_i : \mathbb N \to \mathbb N$ pour $i \ge 0$
$$ B_i(x) = \begin{cases} 1 & \text{si}~i=0, x=0 \\ 2 & \text{si}~i=0, x=1 \\ x+2 & \text{si}~i=0, x \gt 1 \\ {B_{i-1}}^{\langle x \rangle}(1) & \text{si}~i \gt 0 \end{cases} $$
$$ \begin{eqnarray}{} B_0(x) & = & x+2 \quad & \text{si}~x \gt 1 \\ B_1(x) & = & 2x & \text{si}~x \gt 0 \\ B_2(x) & = & 2^x & \text{si}~x \ge 0 \\ B_3(x) & = & \underbrace{2^{2^{2^{\cdots}}}}_{n~\text{fois}} & \text{si}~x \gt 0 \\ \end{eqnarray} $$
Il est clair que plus $i$ est grand, plus $B_i$ est une fonction qui croît rapidement.
Pour tout $i \gt 0$, $B_i$ est calculables par un programme RÉPÉTER.
$\rrmacro{B[0]}{r_1} = B_0(r_1)$
$ \rrinvoke{r_0}{PLUS}{r_1,1} \\ \rrinvoke{r_2}{PG?}{r_0,2} \\ \rrif{r_2} [\\ \quad \rrinc{r_0} \\ ] $
Pour un $i > 0$ fixé, $\rrmacro{B[i]}{r_1} = B_i(r_1)$
$ \rrinc{r_0} \\ \rrrep{r_1} [\\ \quad \rrinvoke{r_0}{B[i-1]}{r_0} \\ ] $
On remarque que le programme $\mathtt{B[i]}$ compte exactement $i$ boucles $\mathtt{répéter}$ et la profondeur d’imbrication est aussi $i$.
Propriétés de la famille des fonctions $B_i$
Preuve: Tous les énoncés du théorème peuvent être facilement prouvés par induction sur $i$.
Définition: Pour tout programme RÉPÉTER, $\mathcal B(\mathtt{P})$ est le nombre maximal d’imbrications des boucles de $\mathtt{P}$.
Définition: On note $\mathcal M(\mathtt{P}, r_1, \dots, r_k)$ la valeur maximale des registres $r_1, \dots, r_k$ après l'exécution de $\mathtt{P}$.
Pour tout programme RÉPÉTER, si $\mathcal B(\mathtt{P}) = i$, alors il existe un entier $s$ tel que
$$ \forall_{r_1, \dots, r_k \in \mathbb N} \ \mathcal M(\mathtt{P}, r_1, \dots, r_k) \le {B_i}^{\langle s \rangle}\big(\max(r_1, \dots, r_k)\big) $$
Pour tout $i \ge 0$ il existe une fonction qui n’est pas calculable par un programme RÉPÉTER avec une profondeur de boucle $i$, mais qui est calculable par un programme avec une profondeur de boucle $i + 1$.
Définition: En 1926, Wilhelm Ackermann définit la fonction à deux variables suivante
$$ A(i,x) = \begin{cases} 1 & \text{si}~x=0 \\ 2 & \text{si}~i=0, x=1 \\ x+2 & \text{si}~i=0, x \gt 1 \\ A(i-1,A(i,x-1)) & \text{si}~i \gt 0, x \gt 0 \end{cases} $$
$$ \forall_{i \in \mathbb N} \ \forall_{x \in \mathbb N} \ A(i,x) = B_i(x) $$
Preuve. Le lemme sera prouvé par induction d’abord sur $i$ et en suite sur $x$.
La fonction d’Ackermann n’est pas calculable par un programme RÉPÉTER.
Donc Ackermann n’est pas primitive récursive.
La fonction $F(x) = A(x, x)$ croît plus rapidement que n’importe quelle des fonctions $B_i(x)$.
Un programme RÉPÉTER ne peut pas entrer dans une boucle infinie, son execution se termine toujours.
Les programmes TANTQUE sont semblables aux programmes RÉPÉTER
Les programmes TANTQUE sont semblables aux programmes RÉPÉTER, mais les boucles sont differentes:
Un programme TANTQUE implante une fonction
$$ \begin{eqnarray} f : & \mathbb N \times \mathbb N \times \cdots \times \mathbb N & \to & \mathbb N \cup \{ \uparrow \} \\ & (r_1, \ r_2, \ \dots, \ r_k) & \mapsto & \begin{cases} r_0 & \text{si le programme s’arrête} \\ \uparrow & \text{si le programme boucle a l’infini} \\ \end{cases} \end{eqnarray} $$
Au debut de l’exécution, les registres $r_1$ à $r_k$ contiennent les arguments de $f$, et à la fin, $r_0$ contient $f(r_1, \dots, r_k)$.
Contrairement aux programmes RÉPÉTER, un programme TANTQUE peut ne jamais s’arrêter, par exemple :
$\rrmacro{BOUCLE}{r_1} = \uparrow$
$ \rrinc{r_1} \\ \rrwhile{r_1 \ne r_0}[\ ] \\ $
Tout programme RÉPÉTER peut être simulé par un programme TANTQUE.
Il suffit de remplacer les boucles de la forme
$\rrrep{r_i} [\dots]$
par (où $r_j$ et $r_k$ sont des registres non utilisés)
$ \rrset{r_k}{r_i} \\ \rrwhile{r_j \ne r_k} [ \\ \quad \dots \\ \quad \rrinc{r_j} \\ ] $
On se permettra d’utiliser les instructions $\mathtt{répéter}$ dans les programmes TANTQUE.
On peut donc recycler comme des programmes TANTQUE tous les programmes RÉPÉTER que nous avons vus.
Nous allons exhiber un programme TANTQUE qui implante la fonction d’Ackermann
$\rrmacro{ACKERMANN}{r_1, r_2} = A(r_1, r_2)$
| $ \rrset{r_3}{1} \\ \rrinc{r4} \quad \rrinvoke{r_3}{TABLASS}{r_3, r_4, r_1} \\ \rrinc{r4} \quad \rrinvoke{r_3}{TABLASS}{r_3, r_4, r_2} \\ \rrwhile{r_4 \ne 1} [ \\ \quad \rrinvoke{r_5}{DEC}{r_4} \quad \rrinvoke{r_7}{TABLEVAL}{r_3, r_5} \\ \quad \rrset{r_6}{r_4} \quad\quad\quad \rrinvoke{r_8}{TABLEVAL}{r_3, r_6} \\ \quad \rrinvoke{r_9}{PG?}{r_8, 0} \quad \rrinvoke{r_{10}}{NEG}{r_9} \\ \quad \rrinvoke{r_{11}}{PG?}{r_7, 0} \quad \rrinvoke{r_{12}}{NEG}{r_{11}} \\ \quad \rrinvoke{r_{13}}{PG?}{r_8, 1} \quad \rrinvoke{r_{14}}{NEG}{r_{13}} \\ \quad \rrif{r_{10}} [\\ \quad\quad \rrinvoke{r_4}{DEC}{r_4} \\ \quad\quad \rrinvoke{r_3}{TABLASS}{r_3, r_4, 1} \\ \quad ] \\ $ | $ \quad \rrif{r_{9}} [\\ \quad\quad \rrif{r_{12}} [\\ \quad\quad\quad \rrif{r_{14}} [ \rrinvoke{r_4}{DEC}{r_4} \ \rrinvoke{r_3}{TABLASS}{r_3, r_4, 2} ] \\ \quad\quad\quad \rrif{r_{15}} [ \\ \quad\quad\quad\quad \rrinvoke{r_{15}}{PLUS}{r_8,2} \quad \rrinvoke{r_4}{DEC}{r_4} \\ \quad\quad\quad\quad \rrinvoke{r_3}{TABLASS}{r_3, r_4, r_{15}} \\ \quad\quad\quad ] \\ \quad\quad ] \\ \quad\quad \rrif{r_{11}} [\\ \quad\quad\quad \rrinvoke{r_{15}}{DEC}{r_7} \quad \rrinvoke{r_3}{TABLASS}{r_3, r_5, r_{15}} \\ \quad\quad\quad \rrinvoke{r_3}{TABLASS}{r_3, r_6, r_{7}} \quad \rrinvoke{r_{15}}{DEC}{r_8} \\ \quad\quad\quad \rrinc{r_4} \quad \rrinvoke{r_3}{TABLASS}{r_3, r_4, r_{15}} \\ \quad\quad ] \\ \quad ] \\ ] \\ \rrinvoke{r_0}{TABLVAL}{r_3, r_4} $ |