Théorème de Post
{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}
{{#invoke:Bandeau|ébauche}}
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).
