Les theoremes de limitation

pages

Français

Documents

Écrit par
Patrick Dehornoy

Publié par
mijec

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

mijec

Nombre de lectures

Langue

Français

Niveau: Supérieur, Doctorat, Bac+8
CHAPITRE VIII Les theoremes de limitation Resume. • Les fonctions primitives recursives s'obtiennent a partir des fonctions cons- tante, successeur et projections par composition et recursion. • La plupart des fonctions usuelles sur Np sont primitives recursives. En particulier, il existe des numerotations primitives recursives des suites d'entiers. • Les fonctions recursives s'obtiennent de meme mais en ajoutant l'operation de mini- malisation. • Les fonctions recursives coıncident avec les fonctions calculables par machine de Tu- ring, donc, modulo la these de Church–Turing, avec les fonctions calculables. • On peut numeroter les formules de la logique du premier ordre de fac¸on a ce que toutes les manipulations syntaxiques correspondent a des fonctions recursives. • Soit PAfaible le systeme de Robinson, qui est le systeme de Peano sans induction mais avec une definition de l'ordre. Il existe des modeles de PAfaible tres differents de (N, 0, S, +, ·), mais tout modele de PAfaible est une extension finale de (N, 0, S, +, ·). • Les formules ?1 sont les formules ou toutes les quantifications universelles sont bornees ?x!y. Toute formule close ?1 vraie dans (N, 0, S, +, ·) est prouvable a partir de PAfaible. • Toute fonction recursive totale f est representable dans PAfaible : il existe une formule F telle que m = f(!n) implique PAfaible F(S!n0,x) ? x = Sm0.