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 $\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 à ∅⁽ⁿ⁾.