Théorème de Post

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie de la calculabilité, le théorème de Post, du nom d'Emil Post, fait le lien entre hiérarchie arithmétique et degré de Turing.

Théorème — Pour tout n > 0 :

  • B appartient à Σn+1 si et seulement si B est récursivement énumérable avec oracle Π n {\displaystyle \Pi _{n}} (ou Σn) ;
  • ∅(n), c'est-à-dire le n-ième degré de Turing après ∅, est Σn-complet.

En particulier :

  • B est dans Σn+1 si et seulement si B est récursivement énumérable avec l'oracle ∅(n) ;
  • B est dans Δn+1 si et seulement si B est Turing-réductible à ∅(n).
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail de la logique
  • icône décorative Portail des mathématiques