Modèles de calcul, TD numéro 4

Natacha Portier lundi 3 mars 2002

Question 1

Nous allons montrer qu’il existe une fonction partiellement récursive qui ne peut pas être prolongée en fonction récursive totale.

Question 1,1 (méthode JM)

Soit A = {i | ϕ_{i}(0) = 0} et B = {i | ϕ_{i}(0) = 1}. Montrer que ces ensembles sont récursivement inséparables.

Question 1,2

Soit ϕ la fonction définie sur A ∪ B qui vaut 0 sur A et 1 sur B. Montrer qu’elle est partiellement récursive et ne peut pas être prolongée en fonction récursive totale.

Question 1,3 (méthode PK)

Soit ϕ la fonction définie sur l’ensemble des numéros de machine de Turing dont le calcul s’arrête sur l’entrée 0, et telle que telle que pour tout entier i la machine de Turing numéro i s’arrête sur l’entrée 0 après ϕ(i) pas de calcul.

Montrer que cette fonction est partiellement récursive et ne peut pas être prolongée en fonction récursive totale.

Question 1,4 (méthode MD)

Soit φ(i) = ϕ_{i}(i) + 1. Montrer que cette fonction est partiellement récursive et ne peut pas être prolongée en fonction récursive totale.

Question 2

Soit Φ_{0}, Φ_{1}, ... un système de programmation acceptable. Soit A = {j|∃xΦ_{j}(x) = j}.

Question 2,1

On dit qu’un ensemble d’entiers E préserve les fonctions si pour tout entier i et j, si i appartient à E et Φ_{i} = Φ_{j} alors j appartient à E. Est-ce que A préserve les fonctions ?

Question 2,2 Est-ce que A est récursif ? Question 2,3 Est-ce que A est récursivement énumérable ? Question 3 Soit Φ_{0}, Φ_{1}, ... un système de programmation acceptable. Question 3,1 Montrer qu’il existe une solution à l’équation :

∀xΦ_{j}(x) = \{ \begin{matrix}2Φ_{x}(x) + 1 & si x > 3j \\ 0 & sinon \end{matrix}

Question 3,2 Soit j la solution de l’équation et A = {x | Φ_{j}(x) diverge}. Est-ce que A est récursivement énumérable ? Question 4 Soit Φ_{0}, Φ_{1}, ... un système de programmation acceptable. Soit f une fonction de N dans N bijective et récursive totale. Question 4,1 L’équation suivante a-t-elle une solution ?

Φ_{j}(x) = \{ \begin{matrix}Φ_{f(x)}(j) & si f(j) > j \\ Φ_{x}(f(j)) & sinon \end{matrix}

Question 4,2 Soit j une solution de l’équation précédente. Soit A = {x|Φ_{j}(x) diverge}. Est-ce que A est récursivement énumérable ?

Question 5,1 Donner un circuit booléen qui calcule la somme de deux entiers y_{n}...y_{1} et x_{n}...x_{1} écrits en base 2 de taille n et évaluer sa taille et sa profondeur. Question 5,2 On améliore la profondeur du circuit précédent de la manière suivante. On suppose que n est une puissance de 2. On calcule en parallèle la somme de y_{n/2}...y_{1} et x_{n/2}...x_{1} ainsi que les sommes y_{n}...y_{n/2+1}+x_{n}...x_{n/2} et y_{n}...y_{n/2+1}+ x_{n}...x_{n/2} + 1, puis on choisit le résultat en fonction de la retenue. Evaluer la taille et la profondeur du circuit. Question 5,3 Généraliser la construction précédente.