Théorème de Post

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 (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
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.