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