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).
- Portail de l'informatique théorique
- Portail de la logique
- Portail des mathématiques
