Théorème de Post
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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).
  • \emptyset^{(n)}, c'est-à-dire le n-ième degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) de Turing après \emptyset, est Σn-complet.

En particulier,

  • B est dans Σn + 1 si et seulement si B est récursivement énumérable (Intuitivement un ensemble est récursivement énumérable s'il existe un procédé mécanique (en gros qui peut être réalisé par un ordinateur) qui liste ses éléments. On dirait aussi qu'il existe un...) avec l'oracle \emptyset^{(n)}.
  • B est dans Δn + 1 si et seulement si B est Turing-réductible à \emptyset^{(n)}.
Page générée en 0.037 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique