correction de l'exercice 1 : construire une machine à
registres pour calculer le reste modulo 3 (et plus
généralement, le reste modulo un entier k > 0 fixé)
1 seul registre suffit, mais pour k > 0 fixé, la taille du programme est quadratique.
Avec 2 registres, on obtient une taille du programme linéaire, mais le temps de calcul est plus long !
correction de l'exercice 2 : construire une machine à registres pour calculer le division euclidienne n, p -> q, r tels que n = p q + r
On utilise 4 registres N, P, Q, R. Au départ, N = n, P = p, Q = 0, R = 0, et à l'arrivée, N = 0, P = p - r -1, Q = q, R = r (mais on peut aussi remettre P à 0).
Dans le cas où p = 0,
la machine boucle, et le registre Q contient des valeurs de plus en
plus grandes. On peut éviter cela en commençant par un
test sur P.
correction de l'exercice 3 : que peut calculer une machine à 1 registre ?
Une machine à 1 registre peut calculer :
la fonction constante n -> k où k est un entier naturel fixé ;
le reste modulo un entier k > 0 fixé ;
plus généralement, une fonction périodique, qui ne dépend que du reste modulo un entier k > 0 fixé ;
la translation n -> n + k, pour un entier k fixé (k peut être négatif, mais dans ce cas, il faut plutôt prendre max(0, n + k)) ;
une fonction définie arbitrairement pour les premières valeurs 0, …, m, puis définie comme ci-dessus pour n > m.
En étudiant le comportement de la machine lorsque le contenu n du registre est infini (c'est-à-dire n suffisamment grand), on arrive à démontrer que ce sont les seules possibilités.
Formalisation
Une machine à k registres et n instructions est une suite de n instructions de l'une des 3 formes suivantes, où l'entier i est dans l'ensemble {0, …, k - 1} et les entiers p, q sont dans l'ensemble {0, …, n -1} :
0 : arrêt
(1, i, p) : incrémenter le registre i, puis aller à l'instruction p
(2, i, p, q) : décrémenter le registre i, puis aller à l'instruction p, ou si le contenu du registre est nul, aller à q
Codage
On définit l'entier naturel <p, q> qui code le couple (p, q) d'entiers naturels, par exemple <p, q> = 2p 3q.
On définit de même le code <p, q, r> d'un triplet (p, q, r), et celui d'un quadruplet. On définit aussi le code [p1, …, pk] d'une suite finie d'entiers naturels.
Machine à registres universelle
On associe à toute machine à registres un entier naturel p qui code la liste des instructions de la machine.
Une machine à registre universelle pour les machines à k registres est une machine à k + 1 + k' registres telle que, si on commence avec :
des entiers naturels x1, … , xk dans les k premiers registres (les données) ;
le code p d'une machine M à k registres dans le registre suivant (le programme), et 0 dans les k' registres auxiliaires ;
alors :
on termine si et seulement si la machine M termine sur les données x1, … , xk ;
on obtient les mêmes résultats que la machine M dans les k premiers registres ;
on finit avec p dans le registre suivant, et 0 dans les k' registres auxiliaires.
Fonctions récursives
correction de l'exercice : construire une machine à registres universelle pour les machines à 2 registres
Fonctions récursives primitives
La classe des fonctions récursives primitives est la plus petite classe de fonctions (totales) f : Np -> N qui contient :
la fonction constante 0 : N0 -> N
la fonction successeurS : N1 -> N
les pprojectionsproj p1, … , proj pp : Np -> N pour tout p dans N
et qui est fermée par les constructions suivantes :
substitution (ou composition généralisée) : g o <f1, … , fq> : Np -> N pour f1, … , fq : Np -> N et g : Nq -> N
récursion primitive : rec (f, g) : Np+1 -> N pour f : Np -> N et g : Np+2 -> N où la fonction h = rec (f, g) est définie ainsi : h (x1, … , xp, 0) = f (x1, … , xp) et h (x1, … , xp, Sy) = g (x1, … , xp, y, h (x1, … , xp, y))
exemples : somme x + y, prédécesseur Px, soustraction tronquée max(x - y, 0), multiplication x x y, factorielle x!, …
contre-exemple : la fonction d'Ackermann, définie par Ack (0, x) = Sx, Ack (Sx, 0) = Ack (x, 1), et Ack (Sx, Sy) = Ack (x, Ack (Sx, y))
Remarque : Cette fonction est obtenue par un argument de diagonalisation. Elle est récursive et prouvablement totale dans l'arithmétique de Peano.
Fonctions récursives
La classe des fonctions récursives est la plus petite classe de fonctions (partielles) f : Np -> N
qui contient les mêmes fonctions et qui est fermée par les
mêmes constructions, avec une construction supplémentaire :
minimisation : minimf : Np -> N pour f : Np+1 -> N où la fonction g = minimf est définie ainsi : g (x1, … , xp) est le plus petit y tel que f (x1, … , xp, y) = 0 et f (x1, … , xp, z) est défini pour tout z < y
Remarques :
en pratique, on calcule successivement f (x1, … , xp, 0), f (x1, … , xp, 1), f (x1, … , xp, 2), … jusqu'à ce qu'on obtienne 0 ;
même si la fonction f est totale, la fonction g peut être indéfinie car la fonction f ne s'annule jamais ;
à cause de cela, on construit une classe de fonctions partielles plutôt qu'une classe de fonctions totales ;
si la fonction f est partielle, la fonction g peut être indéfinie car la fonction f est indéfinie … avant de s'annuler
si on ne rajoutait pas la condition supplémentaire dans la définition de g, on aurait des problèmes dans la suite !
Fonctions récursives et fonctions calculables
Théorème : une fonction est récursive si et seulement si elle est calculable par une machine (à registres, à piles, ou de Turing).
relations ->R, ->*R, <->R, et congruence <->*R engendrée par une relation binaire R sur S* (ensemble des relations ou règles)
monoïde défini par la présentation (S, R) : quotient M = S*/<->*R
Problème des mots : étant donnés une présentation finie (S, R) et deux mots u, v dans S*, a-t-on u <->*R v ?
Dans le cas des groupes, on parle de problème du mot, car on peut toujours se ramener à u <->*R1
Ce problème est indécidable, même si on se limite au problème du mot pour les groupes (Théorème de Novikov-Boone)
Idée : on code le problème de l'arrêt pour les machines à 2 registres
Réécriture convergente
terminaison : une présentation (S, R) est noetherienne si toute réduction termine, c'est-à-dire s'il n'existe pas de réduction infinie u0 ->* u1 ->* u2 ->* … ->* un ->* un+1 ->* …
confluence : une présentation (S, R) est confluente (respectivement localement confluente) si tous les pics v *<- u ->* v' (respectivement v <- u -> v') sont confluents
convergence : une présentation (S, R) est convergente si elle est à la fois noetherienne et confluente
Remarques :
terminaison => existence d'une forme réduite pour tout mot u : il suffit de réduire u autant de fois que nécessaire
confluence => unicité de cette forme réduite ȗ : si v *<- u ->* v' avec v, v' réduits, alors on a v ->* w *<- v', d'où v = w = v'
convergence
=> décidabilité du problème des mots (pour une
présentation finie) : il suffit de comparer les formes
réduites
confluence => confluence locale : c'est évident, car on se limite aux réductions en une étape
Proposition : réciproquement, la confluence locale implique la confluence dans le cas noetherien
Démonstration : par récurrence noetherienne.
Confluence des pic critiques
un chevauchement est un mot uvw tel que uv -> s et vw -> t sont des règles, et v n'est pas vide
une inclusion est un mot uvw tel que uvw et v sont des membres gauches de règles (sans condition supplémentaire)
un pic critique est un chevauchement ou une inclusion
Remarques :
si la présentation est finie, il n'y a qu'un nombre fini de pics critiques
dans le cas d'une présentation finie noetherienne, la confluence des pics critiques est donc décidable
Proposition : la confluence des pics critiques implique la confluence locale
Remarque : pour montrer qu'une présentation est convergente, il suffit donc de vérifier le terminaison (en utilisant un ordre de terminaison) et la confluence des pics critiques
Réécriture de termes du premier ordre et du second ordre (lambda-calcul) : à voir …