Théorème de Post
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
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 à .
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
