Théorème de Post

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Théorème — Pour tout n > 0 :

  • B appartient à Σn+1 si et seulement si B est récursivement énumérable avec oracle \Pi_n (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).