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.
Théorème — Pour tout n > 0 :
- B appartient à Σn+1 si et seulement si B est récursivement énumérable avec oracle (ou Σn) ;
- ∅(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 ∅(n) ;
- B est dans Δn+1 si et seulement si B est Turing-réductible à ∅(n).
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.