Modèles de calcul, TD numéro 3

Natacha Portier vendredi 11 février 2000

Rappel : Un système de programmation est une liste Φ_{0}, Φ_{1}, ... qui inclut toutes les fonctions partiellement récursives d’une variable de N. Un système de programmation est universel s’il existe une fonction partielle récursive Φ_{univ} telle que Φ_{univ}(< i, x >) = Φ_{i}(x) pour tout i et tout x. Cette fonction est appelée fonction universelle partielle récursive. Un système de programmation universel est acceptable s’il vérifie le théorème s − m − n.

Théorème s − m − n: Il existe une fonction totale récursive s telle que pour tout i, pour tout m plus grand que 1 et n plus grand que 1, et pour tous x_{1}, ..., x_{m} et y_{1}, ..., y_{n},

Φ_{s(i,m,x_{1},...,x_{m})}(y_{1}, ..., y_{n}) = Φ_{i}(x_{1}, ..., x_{m}, y_{1}, ..., y_{n})

Question 1

Soit Φ_{0}, Φ_{1}, ... un système de programmation acceptable. Montrer qu’il existe une fonction récursive pl(i, j) telle que pout tous i et j l’entier pl(i, j) soit un indice pour la fonction Φ_{i} + Φ_{j}.

Question 2

Théorème 1 : Un système de programmation universel est acceptable si et seulement s’il existe une fonction totale récursive c telle que Φ_{c(i,j)} = Φ_{i} ∘ Φ_{j} pour tous i et j.

Question 2.1

Montrer le sens direct.

Question 2.2

Soit Φ_{0}, Φ_{1}, ... un système de programmation universel tel qu’il existe une fonction totale récursive c telle que Φ_{c(i,j)} = Φ_{i} ∘ Φ_{j} pour tous i et j.

On définit les fonctions récursives P, Q et R par : P (y) = (0, y), Q(x, y) = (x + 1, y) pour tout x et y, Φ_{p} = P, Φ_{q} = Q, R(0) = p et pour tout x, R(x + 1) = c(q, R(x)).

Montrer que pour tout x et y on a Φ_{R(x)}(y) = (x, y).

Conclure. Question 3 Théorème du point fixe : Soit Φ_{0}, Φ_{1}, ... un système de programmation acceptable. Soit α une fonction récursive primitive à une variable. Alors il existe un entier i tel que Φ_{i} = Φ_{α(i)}.

Montrer le théorème. Question 4 Les fonctions booléennes peuvent s’exprimer en fonction de ET, OU et NON. Question 4.1 Montrer qu’on peut utiliser seulement ET et NON. Question 4.2 On définit les connecteurs NOU et NET par NOU(x, y) = ¬(x ∨ y) et NET (x, y) = ¬(x∧y). Montrer que toute fonction booléenne peut s’exprimer avec NOU seulement. Le montrer pour NET. Question 4.3 Montrer qu’il n’y a pas de connecteur binaire à part ces deux qui permette de tout exprimer (sans utiliser les fonctions constantes VRAI ni FAUX). Question 5 Une fonction booléenne croissante F est une fonction qui a la propriété suivante : si on change une des valeurs de l’entrée de V RAI à F AUX, la valeur de la fonction ne peut pas changer de F AUX à V RAI. Montrer qu’une fonction est croissante si et seulement si elle peut s’exprimer par un circuit qui n’utilise que des portes ET et OU, et les fonctions constantes VRAI et FAUX.