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