Les theoremes de limitation
43 pages
Français

Les theoremes de limitation

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
43 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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.

  • celebres theoremes d'incompletude de godel

  • famille

  • resultats negatifs exprimant des limitations

  • existence de formules vraies dans la structure

  • pafaible de l'arithmetique de peano

  • primitive recursive

  • addition

  • theoremes de limitation

  • pafaible

  • formules pour representer


Sujets

Informations

Publié par
Nombre de lectures 48
Langue Français

Exrait

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents