Piratage Informatique

non n’est pas calculable : c’est «l’ind´cidabilit´ du probl`me de l’arrˆt». e e e e

1

Deux mod`les de calculabilit´ e e

Ces mod`les visent ` capturer le cœur de la notion de calculabilit´. Ils ne se veulent pas r´alistes en ce e a e e sens que – ils ne concernent que les fonctions des entiers naturels dans les entiers naturels – nous verrons toutefois que l’on peut d´j` y d´finir et manipuler des structures de donn´es ; ea e e – ils ne s’int´ressent pas encore ` la notion d’efficacit´ ni d’effectivit´ en temps ou en espace mais e a e e seulement ` la notion de possibilit´ d’un processus de calculs. a e Leur principe est de poser un ensemble minimal de briques de d´part et de moyens de composition ou e combinaison.

1.1

Fonctions r´cursives e

L’ensemble des fonctions «r´cursives» est le plus petit ensemble de fonctions qui contient e R1 les «fonctions constantes» : c(x1 , . . . , xk ) = 0 R2 la fonction «successeur» : s(x) = x + 1 R3 les «projections» : pi (x1 , . . . , xk ) = xi avec 1 ≤ i ≤ k et qui est clos par 1

R4 «composition» : soient h, g1 , . . . , gn des fonctions r´cursives, la fonction f telle que e f (x1 , . . . , xk ) = h(g1 (x1 , . . . , xk ), . . . , gn (x1 , . . . , xk )) est r´cursive. e R5 «sch´ma primitif r´cursif» : soient h et g deux fonctions r´cursives, la fonction f telle que e e e f (0, x1 , . . . , xk ) f (x + 1, x1 , . . . , xk ) = h(x1 , . . . , xk ) = g(x, x1 , . . . , xk , f (x, x1 , . . . , xk ))

est r´cursive. e R6 et «sch´ma de minimisation» : soit g une fonction, on note µx.(g(x1 , . . . , xk , x) = 0) le plus petit x e tel que g(x1 , . . . , xk , x) = 0. Notons qu’un tel x peut ne pas exister. Soit g une fonction r´cursive, la fonction f d´finie par e e f (x1 , . . . , xk ) = µx.(g(x1 , . . . , xk , x) = 0) est r´cursive. e Pour l’intuition informatique : les primitives r´cursives correspondent ` des it´rations born´es (boucles for) e a e e et le sch´ma µ ` des it´rations non born´es (boucles while). e a e e 1.1.1 Primitives r´cursives e

Les fonctions r´cursives d´finies en suivant uniquement les clauses R1 ` R5 sont dites primitives r´cursives. e e a e Plus g´n´ralement, une fonction f est dite primitive r´cursive d´s lors qu’il existe une fonction f d´finie e e e e e selon les clauses R1-R5 telle que pour tout x, f (x) = f (x). Nous donnons dans ce qui suit la d´finitions de quelques fonctions de base et montrons pourquoi elles sont e primitives r´cursives. Et nous donnons ´galement quelques exemples de sch´mas de d´finitions r´cursives e e e e e d’usage courant et nous montrons qu’ils restent dans la classe des primitivs r´cursives. e L’addition est primitive r´cursive. En effet l’addition est d´finie par les ´quations e e e ad(0, y) ad(x + 1, y) = y = s(ad(x, y))

qui ressemblent fort au sch´ma primitif r´cursif. Pour le retrouver rigoureusement, on pose g(y) = p1 (y) = y e e (qui est primitive r´cursive) et h(x, y, z) = s(p3 (x, y, z)) = s(z) (qui est aussi primitive r´cursive). Les e e ´quations de ad deviennent alors e ad(0, y) ad(x + 1, y) = g(y) = h(x, y, ad(x, y))

qui r´pondent exactement au sch´ma primitif r´cursif. e e e La multiplication est primitive r´cursive. La multiplication est d´finie par e e mul(0, y) mul(x + 1, y) = 0 = ad(mul(x, y), y)

Pour s’en convaincre, on prend g(y) = c(y) = 0 et h(x, y, z) = ad(p3 (x, y, z), p2 (x, y, z)) = ad(z, y). Remarque: – on s’autorisera ` utiliser les notations infixes usuelles des fonctions d’addition et de multiplication : a x + y et x · y. Il en ira de mˆme pour les autres fonctions arithm´tiques usuels : soustraction, tests e e d’´galit´, inf´riorit´, etc. ; e e e e – on ne mentionnera plus les usages triviaux des fonctions constantes, des projection ou de la composition dans les sch´mas de d´finition. e e 2

Pr´d´cesseur et soustraction La fonction «pr´d´cesseur» est l’inverse de la fonction successeur, sauf e e e e sur 0 dont, par convention, le pr´d´cesseur est 0. Elle est d´finie par e e e pred(0) pred(x + 1) = 0 = x

et est primitive r´cursive. e La fonction de soustraction enti`re (0−n = 0) est obtenue par it´ration du pr´d´cesseur. Elle est primitive e e e e r´cursive : e sub(x, 0) = x sub(x, y + 1) = pred(sub(x, y)) Fonctions bool´ennes et alternative Les valeurs bool´ennes «vrai» et «faux» sont repr´sent´es (on dit e e e e aussi «cod´es»), respectivement, par n’importe quel entier non nul et 0. e On d´finit les fonctions (primitives r´cursives) not, and et or repr´sentant les fonctions de n´gation, e e e e conjonction et disjonction not(0) = 1 not(x + 1) = 0 and(x1 , x2 ) or(x1 , x2 ) = x1 · x2 = x1 + x2

On pourra noter x1 ∧ x2 pour and(x1 , x2 ) et x1 ∨ x2 pour or(x1 , x2 ). La fonction (primitive r´cursive) alternative (ou «conditionnelle») est d´finie par les ´quations e e e if (0, x1 , x2 ) if (x + 1, x1 , x2 ) L’alternative permet des d´finitions «par cas» : e f (x1 , . . . , xk ) = if (t(x1 , . . . , xk ), f1 (x1 , . . . , xk ), f2 (x1 , . . . , xk )) Si t, f1 et f2 sont primitives r´cursives alors f ´galement. Pour reprendre l’usage, on notera l’´quation e e e ci-dessus comme ci-dessous : f (x1 , . . . , xk ) = f1 (x1 , . . . , xk ) si t(x1 , . . . , xk ) = f2 (x1 , . . . , xk ) sinon Si la fonction f2 est ` son tour une alternative, on utilisera le mˆme racourci d’´criture a e e f (x1 , . . . , xk ) = f1 (x1 , . . . , xk ) si t1 (x1 , . . . , xk ) = f2 (x1 , . . . , xk ) si t2 (x1 , . . . , xk ) = f3 (x1 , . . . , xk ) sinon ad libitum pour toute imbrication d’alternatives de la forme if (t1 , x1 , if (t2 , x2 , if (t3 , x3 , . . .) . . .). It´ration l’«it´r´e» f n d’une fonction f primitive r´cursive est primitive r´cursive. En effet, l’it´r´e n-i`me e e e e e ee e de f est d´finie par induction sur n : f 0 (x) = x et f n+1 (x) = f (f n (x)). Soit alors f ∗ telle que e f ∗ (0, y) f ∗ (x + 1, y) = y = f (f ∗ (x, y)) = x2 = x1

Si f est primitive r´cursive, alors f ∗ ´galement, et on v´rifie ais´ment par induction sur n que f n (x) = e e e e f ∗ (n, x). 3

Voici une seconde forme d’it´ration o` f est une fonction binaire : e u f ∗∗ (0, y) f ∗∗ (x + 1, y) = y = f (x, f ∗∗ (x, y))

Le «d´velopp´» d’une telle it´ration est f (x, f (x − 1, . . . f (1, f (0, y)) . . .)). f ∗∗ est primitive r´cursive si f e e e e l’est. Cette seconde forme d’it´ration permet de voir que la somme et le produit born´s sont primitifs r´cursifs : e e e Σn f (i) i=0 Πn f (i) i=0 avec S(x, y) = f (x) + y et P (x, y) = f (x) · y. La somme et le produit born´s permettent de d´finir des fonctions primitives r´cursives de test pour les e e e quantifications born´es : e ∃z ≤ x.(f (x1 , . . . , xk ) = 0) = Σx .(f (x1 , . . . , xk ) = 0) i=0 ∀z ≤ x.(f (x1 , . . . , xk ) = 0) = Πx .(f (x1 , . . . , xk ) = 0) i=0 En effet, pour l’existensielle, il suffit qu’un des f (x1 , . . . , xk ) = 0 soit non nul pour que la somme soit non nulle ; pour l’universelle, il faut que tous les f (x1 , . . . , xk ) = 0 soient non nuls pour que le produit soit non nul. Modification de param`tres e par soient g, h et i des fonctions primitives r´cursives. La fonction f d´finie e e f (0, y) f (x + 1, y) = g(y) = h(x, y, f (x, i(y))) = S ∗∗ (n, 0) = P ∗∗ (n, 1)

est primitive r´cursive. e Ce sch´ma n’est pas primitif ` cause du i(y) dans l’appel r´cursif. Cependant, si l’on «d´roule» le calcul e a e e de f en suivant les ´quations, on obtient e f (x + 1, y) = h(x, y, f (x, i(y)) = h(x, y, h(x − 1, i(y), f (x − 1, i2 (y)))) = h(x, y, h(x − 1, i(y), h(x − 2, i2 (y), f (x − 2, i3 (y))))) . . . = h(x, y, h(x − 1, i(y), h(x − 2, i2 (y), . . . f (1, ix−1 (y)))) . . .) = h(x, y, h(x − 1, i(y), h(x − 2, i2 (y), . . . , h(1, ix−1 (y), f (0, ix (y))) . . .))) = h(x, y, h(x − 1, i(y), h(x − 2, i2 (y), . . . , h(1, ix−1 (y), g(ix (y))) . . .))) On remarque dans ce d´veloppement que pour chaque application de h, si le premier argument est x − k, e le deuxi`me est ik (y). En d’autres termes, si x0 est la valeur initiale de x, ` chaque application de h, on a e a h(x, ix0 −x (i), . . .). Posons h (x, x0 , y, z) = h(x, ix0 −(x+1) (y), z). On note ´galement que l’argument pass´ ` g e ea est ix0 (y). Soit alors f telle que f (0, x0 , y) f (x + 1, x0 , y) = g(ix0 (y)) = h (x, x0 , y, f (x, x0 , y))

qui est primitive r´cursive. e On peut montrer par r´curence sur x que pour tout k, f (x, x + k, y) = f (x, ik (y)) (exercice). On pose e alors f (x, y) = f (x, x, y) ce qui fait de f une fonction primitive r´cursive. e

4

En faisant appel ` la seconde forme d’it´ration donn´e ci-dessus, on peut v´rifier que la forme plus g´n´rale a e e e e e de d´finition avec modification de param`tre e e f (0, y) f (x + 1, y) est primitive r´cursive (exercice). e e Exercice: Soient g, h1 , i1 , h2 , i2 , r primitives r´cursive, montrer que la fonction f telle que f (0, y) f (x + 1, y) est primitive r´cursive. e Comparaisons la comparaison la plus primitive est le test d’´galit´ ` z´ro. Il se d´finit simplement e ea e e eqz(0) eqz(x + 1) C’est en fait la n´gation neg. e De l’´galit´ ` z´ro, on tire le test g´n´ral d’´galit´ entre deux