Théorème de Post - Définition

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).
• , 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 à .