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.

Cet article est orphelin. Il a peu ou aucun article lié à lui. (novembre 2011) Aidez à ajouter des liens dans les articles relatifs au sujet.

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 (en).

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

• B appartient à Σ_n+1 si et seulement si B est récursivement énumérable avec oracle $\Pi_n$ (ou Σ_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 ∅⁽ⁿ⁾ ;
• B est dans Δ_n+1 si et seulement si B est Turing-réductible à ∅⁽ⁿ⁾.