Théorème de post

Théorème de post

Théorème de Post

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é 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 avec l'oracle \emptyset^{(n)}.
  • B est dans Δn + 1 si et seulement si B est Turing-réductible à \emptyset^{(n)}.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Th%C3%A9or%C3%A8me de Post ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de post de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Théorème de Post — 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… …   Wikipédia en Français

  • Theoreme d'incompletude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude — de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les… …   Wikipédia en Français

  • Théorème d'incomplétude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude de Gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'incomplétude de gödel — Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les propositions …   Wikipédia en Français

  • Théorème d'indécidabilité — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Gödel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème de Szemerédi — En mathématiques, le théorème de Szemerédi[1] est la conjecture d Erdős Turán démontrée par Endre Szemerédi en 1975. Sommaire 1 Énoncé 2 Historique …   Wikipédia en Français

  • Emil Post — Pour les articles homonymes, voir Post. Emil Leon Post Emil Leon Post (né le 11 février 1897 à Augustów et mort le 21 avril 1954 à New York) est un mathématicien …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”