Modèles de calcul, TD numéro 1

Natacha Portier mardi 15 janvier 2002

Rappel : un algorithme de Markov M sur l’alphabet A_{k} = {a_{1}, ..., a_{k}} défini par la suite ordonnée finie de règles de production :

p_{1} →_{(t)} q_{1} ; ⋮ ; p_{n} →_{(t)} q_{n}

où chaque p_{i} et q_{i} est un mot de A_{k}^{∗} et (t) signifie qu’une flèche est ou non marquée par t selon que la règle est ou non terminale.

Question 1 Donner un algorithme de Markov qui calcule la fonction successeur des entiers écrits en binaire.

Question 2 Donner un algorithme de Markov qui calcule la fonction prédécesseur des entiers écrits en binaire.

Question 3 Donner un algorithme de Markov qui à partie d’un mot écrit en binaire x_{1}...x_{n} calcule x_{n}...x_{1}.

Question 4 Donner un algorithme de Markov qui accepte les palindromes écrits en binaire.

Rappel : les fonctions partiellement récursives sont obtenues à partir des fonctions de base :

1) La fonction constante égale au mot vide

2) La fonction de concaténation avec la lettre a_{j}

3) Les projections en appliquant un nombre fini de règles de construction suivantes (si la minimisation n’est pas utilisée, la fonction est totale et primitive récursive) :

4) La composition (ou substitution)

5) La définition récursive

6) La minimisation et nous pouvons également utiliser :

7) La définition par cas

8) Les quantifications bornées (∃y/x : il existe un segment initial y de x)

Pour une fonction, les quatre propriétés suivantes sont équivalentes :

1) être partiellement récursive (=semi-calculable)

2) être calculable par une RAM

3) être calculable par une machine de Turing

4) être calculable par un algorithme de Markov

Question 5

Nous allons montrer que la quatrième implique la première.

Question 5,1

Montrer que les prédicats ou fonctions suivants sont primitifs récursifs :

1) Oc(x, y) ssi x est un facteur de y

2) u(x, z) est le mot à gauche de l’occurence de x la plus à gauche dans z si Oc(x, z) et n’importe quoi sinon.

3) v(x, z) est le mot à droite de l’occurence de x la plus à gauche dans z si Oc(x, z) et n’importe quoi sinon.

4) rep(x, y, z) est le mot obtenu en remplaçant dans z l’occurence de x la plus à gauche par y si Oc(x, z) et n’importe quoi sinon.

Question 5,2

Montrer que pour tout algorithme de Markov M les fonctions et prédicats suivants sont primitifs récursifs :

1) m telle que m(x, y) = z si z est obtenu en |y| étapes à partir de x et n’importe quoi sinon.

2) T erm_{M}(x) si et seulement s’il existe y tel que M transforme x en y de manière terminale en une seule étape.

3) Stop_{M}(x, y) ssi M à partir de x s’arrête en |y| étapes.

Question 5,3

Montrer que toute fonction calculable par un algorithme de Markov est partiellement récursive.

De plus, si nous avons un algorithme de Markov et un entier m, nous pouvons en pratique trouver une définition (à partir des fonctions de base et de substitutions, récursions et minimisations) de la fonction partielle de m variables calculée par l’algorithme de Markov.

Question 5,4

Montrer que pour toute fonction partiellement récursive ϕ il existe des fonctions primitives récursives f et g telles que :

ϕ = f ∘ min_{1}g