Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Td 1 corrige Université Paris Diderot UFR de mathématiques Année ?? Logique et complexité TD ?? Fonctions récursives primitives Exercice Montrer que pour tout n ?? N l ? ensemble n est récursif primitif En déduire que tout sous-ensemble de N qui est ?ni o

Université Paris Diderot UFR de mathématiques Année ?? Logique et complexité TD ?? Fonctions récursives primitives Exercice Montrer que pour tout n ?? N l ? ensemble n est récursif primitif En déduire que tout sous-ensemble de N qui est ?ni ou qui est le complémentaire d ? un sous-ensemble ?ni de N est récursif primitif Solution de l ? exercice On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive On sait que l ? égalité f dé ?nie par f x y si x y et sinon est récursive primitive Si on note cn la fonction constante égale à n à une variable on a ? n f ? cn ce qui montre que n est bien un ensemble récursif primitif L ? ensemble des ensembles récursifs primitifs étant clos par opérations booléennes un sous ensemble ?ni de N est la réunion de singletons de N qui sont récursifs primitifs et donc est récursif primitif De même les ensembles co ?nis de N sont récursifs primitif par passage au complémentaire Exercice Montrer que l ? ensemble des nombres pairs est récursif primitif Solution de l ? exercice La fonction caractéristique f des nombres pairs se dé ?nit de la manière suivante par récurrence f et f n ?? f n elle est donc bien récursive primitive Exercice Soit p un entier non nul Montrer que la fonction supp Np ? N qui à x xp associe le maximum de x xp est récursive primitive Solution de l ? exercice Soit p un entier non nul on veut montrer que la fonction supp qui au p-uplet x xp associe le plus grand des xi pour i appartenant à p On fait une démonstration par récurrence sur p sup x x sup ? c ? est la projection à un argument On suppose que les supi pour i appartenant à p ?? sont récursives primitives on regarde pour supp supp x xp sup supp x xp xp o? sup x y x si x y et y sinon Ainsi supp est récursive primitive Donc la fonction supp est récursive primitive pour tout p ?? N ? Exercice Montrer que les fonctions quotient et reste sont récursives primitives par dé ?nition on pose x y si y En déduire que x y y divise x est récursif primitif Solution de l ? exercice Notons q la fonction quotient On a q x y k x k y x donc q est récursive primitive La fonction reste est égale à r x y x ?? yq x y l ? est également Exercice Montrer que l ? ensemble des nombre premiers est récursif primitif En déduire que la fonction ? qui à n fait correspondre le n -ième nombre premier est récursive primitive Solution de l ? exercice Un entier n est premier ssi n et pour tout a ?? n ?? a ne divise pas n qui peut s ? écrire pour tout a n