In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

PropertyValue
dbpprop:abstract
  • In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
  • Postova věta Množina M je rekurzivní právě tehdy, pokud jsou jak M, tak její doplněk rekurzivně spočetné Predikát P je ORP právě tehdy, pokud je P a jeho doplněk RSP
  • Théorème: pour tout n>0 B appartient à <math>\Sigma_{n+1}</math> si et seulement si B est récursivement énumérable avec oracle <math>\Pi_n</math> (ou <math>\Sigma_n</math>). <math>\emptyset^{(n)}</math>, c'est-à-dire le n-ième degré de Turing après <math>\emptyset</math>, est <math>\Sigma_n</math>-complet. En particulier, * B est dans <math>\Sigma_{n+1}</math> si et seulement si B est récursivement énumérable avec l'oracle <math>\emptyset^{(n)}</math>. B est dans <math>\Delta_{n+1}</math> si et seulement si B est Turing-réductible à <math>\emptyset^{(n)}</math>.
  • ポストの定理（英: Post's theorem）は、再帰理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
  • Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом. В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста. Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством <math>\mathsf{B}=\{0,1\}</math>) принадлежит А. И. Мальцеву.
dbpprop:hasPhotoCollection
rdfs:comment
  • In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
  • Postova věta Množina M je rekurzivní právě tehdy, pokud jsou jak M, tak její doplněk rekurzivně spočetné Predikát P je ORP právě tehdy, pokud je P a jeho doplněk RSP
  • Théorème: pour tout n>0 B appartient à <math>\Sigma_{n+1}</math> si et seulement si B est récursivement énumérable avec oracle <math>\Pi_n</math> (ou <math>\Sigma_n</math>). <math>\emptyset^{(n)}</math>, c'est-à-dire le n-ième degré de Turing après <math>\emptyset</math>, est <math>\Sigma_n</math>-complet.
  • ポストの定理（英: Post's theorem）は、再帰理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
  • Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию.
rdfs:label
  • Post's theorem
  • Postova věta
  • Théorème de Post
  • ポストの定理
  • Критерий Поста
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of