Accueil🇫🇷Chercher

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.