Théorème de Post

Ce théorème fait le lien entre hiérarchie arithmétique et degré de Turing.

Théorème (Post): pour tout n>0

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

En particulier,

• B est dans Σ_{n + 1} si et seulement si B est récursivement énumérable avec l'oracle $\emptyset^{(n)}$.
• B est dans Δ_{n + 1} si et seulement si B est Turing-réductible à $\emptyset^{(n)}$.